链接:https://acm.hdu.edu.cn/showproblem.php?pid=2544
package main import ( "fmt" "math" ) var ( n int //n个点 m int //m条边 edge [][]int ) func dij(st, ed int) { vis := make([]bool, n) dis := make([]int, n) for i := 0; i < n; i++ { dis[i] = edge[st][i] } vis[st] = true for i := 0; i < n; i++ { if vis[ed] { break } minn := math.MaxInt64 v := -1 for j := 0; j < n; j++ { if !vis[j] && dis[j] < minn { minn = dis[j] v = j } } vis[v] = true for j := 0; j < n; j++ { if !vis[j] && dis[v] + edge[v][j] < dis[j] { dis[j] = dis[v] + edge[v][j] } } } fmt.Println(dis[ed]) } func main() { for { fmt.Scanf("%d %d", &n, &m) if n == 0 && m == 0 { break } edge = make([][]int, n) for i := 0; i < n; i++ { edge[i] = make([]int, n) } for i := 0; i < n; i++ { for j := 0; j < n; j++ { if i == j { edge[i][j] = 0 } else { edge[i][j] = math.MaxInt64 } } } for i := 0; i < m; i++ { var ( a int b int c int ) fmt.Scanf("%d %d %d", &a, &b, &c) a-- b-- edge[a][b] = int(math.Min(float64(edge[a][b]), float64(c))) edge[b][a] = edge[a][b] } //fmt.Println(edge) dij(0, n - 1) } }