力扣题解 1928

题目描述（困难）

规定时间内到达终点的最小费用

一个国家有 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 。

在这里插入图片描述

要解决这个问题，我们可以使用动态规划结合图的最短路径算法来实现。我们需要在给定的时间限制内，从起点城市（城市0）到达终点城市（城市n-1），并且在此过程中使得经过的所有城市的通行费之和最小。

解题思路

图的表示：用邻接表来表示城市之间的道路。对于每个城市，存储它可以到达的其他城市及对应的时间。
动态规划状态定义：定义一个二维数组 dp[i][t]，表示在时间 t 时到达城市 i 的最小费用。
初始状态：dp[0][0] = passingFees[0]，表示从城市0出发，时间为0时，费用为经过城市0的费用。
状态转移：
- 遍历每一条边 (xi, yi, timei)，如果从城市 xi 到城市 yi 的时间 timei 加上当前时间 t 不超过 maxTime，则更新 dp[yi][t + timei] 为 min(dp[yi][t + timei], dp[xi][t] + passingFees[yi])。
- 同时也从 yi 到 xi 做同样的更新（因为是双向道路）。
结果计算：遍历所有可能的时间 t，找到 dp[n-1][t] 的最小值，即为从城市0到城市n-1的最小费用。
无法到达的情况：如果在所有时间内，dp[n-1][t] 都没有被更新，则返回 -1。

解题分析

时间复杂度：由于需要遍历所有的边，并且对于每个城市需要遍历所有可能的时间，时间复杂度为 (O(E \times T))，其中 (E) 是边的数量，(T) 是 maxTime。
空间复杂度：需要存储一个二维数组 dp，空间复杂度为 (O(n \times T))。

C++代码示例

int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {int n = passingFees.size();vector<vector<pair<int, int>>> graph(n);// Build the graphfor (const auto& edge : edges) {int u = edge[0], v = edge[1], time = edge[2];graph[u].emplace_back(v, time);graph[v].emplace_back(u, time);}// DP arrayvector<vector<int>> dp(n, vector<int>(maxTime + 1, INT_MAX));dp[0][0] = passingFees[0];// Min-Heap to store (cost, time, city)priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;pq.emplace(passingFees[0], 0, 0);while (!pq.empty()) {auto [cost, time, city] = pq.top();pq.pop();if (city == n - 1) {return cost;}for (const auto& [nextCity, travelTime] : graph[city]) {int newTime = time + travelTime;if (newTime <= maxTime) {int newCost = cost + passingFees[nextCity];if (newCost < dp[nextCity][newTime]) {dp[nextCity][newTime] = newCost;pq.emplace(newCost, newTime, nextCity);}}}}return -1;
}