2022-01-06：N个结点之间，表世界存在双向通行的道路，里世界存在双向通行的传送门.
若走表世界的道路，花费一分钟.
若走里世界的传送门，不花费时间，但是接下来一分钟不能走传送门.
输入： T为测试用例的组数，对于每组数据:
第一行：N M1 M2 N代表结点的个数1到N
接下来M1行 每行两个数，u和v，表示表世界u和v之间存在道路.
接下来M2行 每行两个数，u和v，表示里世界u和v之间存在传送门.
现在处于1号结点，最终要到达N号结点，求最小的到达时间 保证所有输入均有效，不存在环等情况 。
来自网易互娱。
答案2022-01-06：
单元最短路径问题。小根堆。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
"sort"
)
func main() {
roads := [][]int{{1}, {2}, {0}}
gates := [][]int{{1}, {2}, {0}}
ret := fast(3, roads, gates)
fmt.Println(ret)
}
// 城市编号从0开始，编号对应0~n-1
// roads[i]是一个数组，表示i能走路达到的城市有哪些，每条路都花费1分钟
// gates[i]是一个数组，表示i能传送达到的城市有哪些
// 返回从0到n-1的最少用时
func fast(n int, roads, gates [][]int) int {
distance := make([][]int, 2)
for i := 0; i < 2; i++ {
distance[i] = make([]int, n)
}
// 因为从0开始走，所以distance[0][0] = 0, distance[1][0] = 0
// distance[0][i] -> 0 : 前一个城市到达i，是走路的方式, 最小代价，distance[0][i]
// distance[1][i] -> 1 : 前一个城市到达i，是传送的方式, 最小代价，distance[1][i]
for i := 1; i < n; i++ {
distance[0][i] = math.MaxInt64
distance[1][i] = math.MaxInt64
}
// 小根堆，根据距离排序，距离小的点，在上！
//PriorityQueue<Node> heap = new PriorityQueue<>((a, b) -> a.cost - b.cost);
heap := make([]*Node, 0)
//heap.add(new Node(0, 0, 0));
heap = append(heap, NewNode(0, 0, 0))
//boolean[][] visited = new boolean[2][n];
visited := make([][]bool, 2)
for i := 0; i < 2; i++ {
visited[i] = make([]bool, n)
}
for len(heap) > 0 {
sort.Slice(heap, func(i, j int) bool {
return heap[i].cost < heap[j].cost
})
//Node cur = heap.poll();
cur := heap[0]
heap = heap[1:]
if visited[cur.preTransfer][cur.city] {
continue
}
visited[cur.preTransfer][cur.city] = true
// 走路的方式
for _, next := range roads[cur.city] {
if distance[0][next] > cur.cost+1 {
distance[0][next] = cur.cost + 1
heap = append(heap, NewNode(0, next, distance[0][next]))
}
}
// 传送的方式
if cur.preTransfer == 0 {
for _, next := range gates[cur.city] {
if distance[1][next] > cur.cost {
distance[1][next] = cur.cost
heap = append(heap, NewNode(1, next, distance[1][next]))
}
}
}
}
return getMin(distance[0][n-1], distance[1][n-1])
}
type Node struct {
preTransfer int
city int
cost int
}
func NewNode(a, b, c int) *Node {
res := &Node{}
res.preTransfer = a
res.city = b
res.cost = c
return res
}
func getMin(a, b int) int {
if a < b {
return a
} else {
return b
}
}
执行结果如下：
左神java代码
