规定时间内到达终点的最小花费
难度:
标签:
题目描述
一个国家有 n 个城市，城市编号为 0 到 n - 1 ，题目保证 所有城市 都由双向道路 连接在一起 。道路由二维整数数组 edges 表示，其中 edges[i] = [xi, yi, timei] 表示城市 xi 和 yi 之间有一条双向道路，耗费时间为 timei 分钟。两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。
每次经过一个城市时，你需要付通行费。通行费用一个长度为 n 且下标从 0 开始的整数数组 passingFees 表示，其中 passingFees[j] 是你经过城市 j 需要支付的费用。
一开始，你在城市 0 ，你想要在 maxTime 分钟以内 （包含 maxTime 分钟）到达城市 n - 1 。旅行的 费用 为你经过的所有城市 通行费之和 （包括 起点和终点城市的通行费）。
给你 maxTime，edges 和 passingFees ，请你返回完成旅行的 最小费用 ，如果无法在 maxTime 分钟以内完成旅行，请你返回 -1 。
示例 1：
输入：maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3] 输出：11 解释：最优路径为 0 -> 1 -> 2 -> 5 ，总共需要耗费 30 分钟，需要支付 11 的通行费。
示例 2：
输入：maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3] 输出：48 解释：最优路径为 0 -> 3 -> 4 -> 5 ，总共需要耗费 26 分钟，需要支付 48 的通行费。 你不能选择路径 0 -> 1 -> 2 -> 5 ，因为这条路径耗费的时间太长。
示例 3：
输入：maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3] 输出：-1 解释：无法在 25 分钟以内从城市 0 到达城市 5 。
提示：
1 <= maxTime <= 1000n == passingFees.length2 <= n <= 1000n - 1 <= edges.length <= 10000 <= xi, yi <= n - 11 <= timei <= 10001 <= passingFees[j] <= 1000- 图中两个节点之间可能有多条路径。
- 图中不含有自环。
代码结果
运行时间: 108 ms, 内存: 16.9 MB
// Java solution using Streams
// 思路：使用Dijkstra算法找到在maxTime以内从起点到终点的最小通行费用，利用Streams简化代码
import java.util.*;
import java.util.stream.*;
public class Solution {
public int minCost(int maxTime, int[][] edges, int[] passingFees) {
int n = passingFees.length;
int[][] graph = new int[n][n];
Arrays.stream(graph).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
Arrays.stream(edges).forEach(edge -> {
int u = edge[0], v = edge[1], time = edge[2];
graph[u][v] = graph[v][u] = Math.min(graph[u][v], time);
});
int[][] dp = new int[n][maxTime + 1];
Arrays.stream(dp).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
dp[0][0] = passingFees[0];
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{0, passingFees[0], 0}); // {city, cost, time}
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int city = curr[0], cost = curr[1], time = curr[2];
if (city == n - 1) return cost;
IntStream.range(0, n).filter(next -> graph[city][next] != Integer.MAX_VALUE)
.forEach(next -> {
int newTime = time + graph[city][next];
if (newTime > maxTime) return;
int newCost = cost + passingFees[next];
if (newCost < dp[next][newTime]) {
dp[next][newTime] = newCost;
pq.offer(new int[]{next, newCost, newTime});
}
});
}
return -1;
}
}解释
方法:
本题使用了带有优先队列的 Dijkstra 算法来寻找在规定时间内从起点到终点的最小费用路径。首先，构建一个图来表示城市之间的道路和通行时间。然后，使用 Dijkstra 算法，通过优先队列来优先处理费用较小的路径。在遍历过程中，记录每个节点到起点的最小费用和最短时间，如果到达某个节点的路径费用更小或者时间更短，则更新该节点的信息并将其加入优先队列中继续遍历。最终，如果能在规定时间内到达终点，则返回最小费用，否则返回 -1。
时间复杂度:
O(E + VlogV)
空间复杂度:
O(V + E)
代码细节讲解
🦆
为什么在实现中使用了优先队列（最小堆），而不是普通的队列或栈来执行Dijkstra算法？
▷🦆
在更新节点信息时，为何同时需要检查`costFromSrc`和`timeFromSrc`是否优于当前记录的最小值？
▷🦆
函数中对于`if costFromSrc > nodeNumTo[curNodeID] and timeFromSrc > distTo[curNodeID]`的条件检查是如何帮助提高算法效率的？
▷🦆
在处理多条相同起点和终点但耗时不同的道路时，Dijkstra算法如何确保找到最优路径？
▷