2022-03-11：int n, int[][] roads, int x, int y，
n表示城市数量，城市编号0~n-1，
roads[i][j] == distance，表示城市i到城市j距离为distance(无向图)，
求城市x到城市y的最短距离。
答案2022-03-11：
有向图，没有负数环。小根堆。
代码用golang编写。代码如下：
package main import ( "fmt" "math" "sort" ) func main() { roads := [][]int{{1, 2, 3}, {1, 3, 5}, {2, 3, 1}} n := 3 x := 1 y := 3 ret := minDistance2(n, roads, x, y) fmt.Println(ret) } func minDistance2(n int, roads [][]int, x, y int) int { // 之一步生成邻接矩阵 map0 := make([][]int, n+1) for i := 0; i < n+1; i++ { map0[i] = make([]int, n+1) } for i := 0; i <= n; i++ { for j := 0; j <= n; j++ { map0[i][j] = math.MaxInt64 } } // 建立路！ for _, road := range roads { map0[road[0]][road[1]] = getMin(map0[road[0]][road[1]], road[2]) map0[road[1]][road[0]] = getMin(map0[road[1]][road[0]], road[2]) } // computed[i] = true，表示从源出发点到i这个城市，已经计算出最短距离了 // computed[i] = false，表示从源出发点到i这个城市，还没有计算出最短距离 computed := make([]bool, n+1) // 距离小根堆 //PriorityQueue<Node> heap = new PriorityQueue<>((a, b) -> (a.pathSum - b.pathSum)); heap0 := make([]*Node, 0) heap0 = append(heap0, NewNode(x, 0)) for len(heap0) > 0 { // x -> ... -> 当前的城市, 有距离 sort.Slice(heap0, func(i, j int) bool { a := heap0[i] b := heap0[j] return a.pathSum < b.pathSum }) cur := heap0[0] heap0 = heap0[1:] if computed[cur.city] { continue } // 没算过 // 开始算！ if cur.city == y { return cur.pathSum } computed[cur.city] = true for next := 1; next <= n; next++ { if next != cur.city && map0[cur.city][next] != math.MaxInt64 && !computed[next] { heap0 = append(heap0, NewNode(next, cur.pathSum+map0[cur.city][next])) } } } return math.MaxInt64 } func getMin(a, b int) int { if a < b { return a } else { return b } } // 当前来到的Node，注意这不是城市的意思，这是就是一个普通的封装类 // Node封装了，当前来到的城市是什么，以及，从源出发点到这个城市的路径和是多少？ type Node struct { // 当前来到的城市编号 city int // 从源出发点到这个城市的路径和 pathSum int } func NewNode(c, p int) *Node { ans := &Node{} ans.city = c ans.pathSum = p return ans }
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2021_12_1_week/Code01_XtoYMinDistance.java)
