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 } // 小根堆,根据距离排序,距离小的点,在上! //PriorityQueueheap = 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代码
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)