2022-03-11：int n, int[][] roads, int x, int y， n表示城市数

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编写。代码如下：

```go

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)