leetcode-go/oj/algorithms/graph/floyd.go

package main

import (
	"fmt"
	"math"
)

func main() {
	var n, m, src int
	fmt.Scan(&n, &m, &src)
	adj := make([][]int, n)
	length := make([][]int, n)
	for i := range length {
		length[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		var u, v, l int
		fmt.Scan(&u, &v, &l)
		adj[u] = append(adj[u], v)
		length[u][v] = l
	}
	fmt.Println(floyd(adj, length))
}

func floyd(adj [][]int, length [][]int) [][]int {
	n := len(adj)
	dist := make([][]int, n)
	for i := range dist {
		dist[i] = make([]int, n)
		for j := range dist[i] {
			dist[i][j] = math.MaxInt32
		}
	}
	for u := range adj {
		for _, v := range adj[u] {
			dist[u][v] = length[u][v]
		}
	}
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if alt := dist[i][k] + dist[k][j]; alt < dist[i][j] {
					dist[i][j] = alt
				}
			}
		}
	}
	return dist
}