1928. 在规定时间内到达目的地的最小花费

Hard

题目描述

有一个包含 n 个城市的国家，城市编号为 0 到 n - 1，所有城市之间都有双向道路连接。道路用二维整数数组 edges 表示，其中 edges[i] = [xi, yi, timei] 表示城市 xi 和 yi 之间有一条需要 timei 分钟才能通过的道路。可能有多条不同旅行时间的道路连接同样的两个城市，但没有道路连接城市到自身。

每次通过一个城市时，你必须支付过路费。这用一个长度为 n 的 0 索引整数数组 passingFees 表示，其中 passingFees[j] 是通过城市 j 时必须支付的美元数。

开始时，你在城市 0，想要在 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 <= 1000
n == passingFees.length
2 <= n <= 1000
n - 1 <= edges.length <= 1000
0 <= xi, yi <= n - 1
1 <= timei <= 1000
1 <= passingFees[j] <= 1000

解题思路

这道题是一个带约束的最短路径问题。我们需要在时间限制内找到从城市0到城市n-1的最小费用路径。

思路分析：

可以使用动态规划来解决这个问题。定义 dp[t][i] 表示在时间 t 内到达城市 i 的最小费用。

状态转移方程：

初始状态：dp[0][0] = passingFees[0]（在时间0时，在城市0的费用就是城市0的过路费）
转移方程：对于每条边 (u, v, time)，如果当前时间加上边的时间不超过最大时间，则可以从城市u转移到城市v

算法步骤：

初始化dp数组，dp[t][i] 表示在时间t到达城市i的最小费用
设置初始状态：dp[0][0] = passingFees[0]
对于每个时间t从0到maxTime，遍历所有边，尝试更新状态
最终答案是 min(dp[t][n-1]) for t in [0, maxTime]

这种方法的优势是能够处理图中的环路和多条路径，确保找到全局最优解。时间复杂度为O(maxTime × edges)，空间复杂度为O(maxTime × n)。

代码实现

class Solution {
public:
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
        int n = passingFees.size();
        vector<vector<int>> dp(maxTime + 1, vector<int>(n, INT_MAX));
        
        dp[0][0] = passingFees[0];
        
        for (int t = 1; t <= maxTime; t++) {
            for (int i = 0; i < n; i++) {
                dp[t][i] = dp[t-1][i];
            }
            
            for (auto& edge : edges) {
                int u = edge[0], v = edge[1], time = edge[2];
                if (t >= time) {
                    if (dp[t-time][u] != INT_MAX) {
                        dp[t][v] = min(dp[t][v], dp[t-time][u] + passingFees[v]);
                    }
                    if (dp[t-time][v] != INT_MAX) {
                        dp[t][u] = min(dp[t][u], dp[t-time][v] + passingFees[u]);
                    }
                }
            }
        }
        
        int result = INT_MAX;
        for (int t = 0; t <= maxTime; t++) {
            result = min(result, dp[t][n-1]);
        }
        
        return result == INT_MAX ? -1 : result;
    }
};

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        n = len(passingFees)
        dp = [[float('inf')] * n for _ in range(maxTime + 1)]
        
        dp[0][0] = passingFees[0]
        
        for t in range(1, maxTime + 1):
            for i in range(n):
                dp[t][i] = dp[t-1][i]
            
            for u, v, time in edges:
                if t >= time:
                    if dp[t-time][u] != float('inf'):
                        dp[t][v] = min(dp[t][v], dp[t-time][u] + passingFees[v])
                    if dp[t-time][v] != float('inf'):
                        dp[t][u] = min(dp[t][u], dp[t-time][v] + passingFees[u])
        
        result = min(dp[t][n-1] for t in range(maxTime + 1))
        return result if result != float('inf') else -1

public class Solution {
    public int MinCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.Length;
        int[,] dp = new int[maxTime + 1, n];
        
        for (int t = 0; t <= maxTime; t++) {
            for (int i = 0; i < n; i++) {
                dp[t, i] = int.MaxValue;
            }
        }
        
        dp[0, 0] = passingFees[0];
        
        for (int t = 1; t <= maxTime; t++) {
            for (int i = 0; i < n; i++) {
                dp[t, i] = dp[t-1, i];
            }
            
            foreach (var edge in edges) {
                int u = edge[0], v = edge[1], time = edge[2];
                if (t >= time) {
                    if (dp[t-time, u] != int.MaxValue) {
                        dp[t, v] = Math.Min(dp[t, v], dp[t-time, u] + passingFees[v]);
                    }
                    if (dp[t-time, v] != int.MaxValue) {
                        dp[t, u] = Math.Min(dp[t, u], dp[t-time, v] + passingFees[u]);
                    }
                }
            }
        }
        
        int result = int.MaxValue;
        for (int t = 0; t <= maxTime; t++) {
            result = Math.Min(result, dp[t, n-1]);
        }
        
        return result == int.MaxValue ? -1 : result;
    }
}

var minCost = function(maxTime, edges, passingFees) {
    const n = passingFees.length;
    const graph = Array(n).fill().map(() => []);
    
    for (const [u, v, time] of edges) {
        graph[u].push([v, time]);
        graph[v].push([u, time]);
    }
    
    const dp = Array(n).fill().map(() => Array(maxTime + 1).fill(Infinity));
    dp[0][0] = passingFees[0];
    
    for (let t = 0; t <= maxTime; t++) {
        for (let u = 0; u < n; u++) {
            if (dp[u][t] === Infinity) continue;
            
            for (const [v, travelTime] of graph[u]) {
                if (t + travelTime <= maxTime) {
                    dp[v][t + travelTime] = Math.min(dp[v][t + travelTime], dp[u][t] + passingFees[v]);
                }
            }
        }
    }
    
    let result = Infinity;
    for (let t = 0; t <= maxTime; t++) {
        result = Math.min(result, dp[n - 1][t]);
    }
    
    return result === Infinity ? -1 : result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(maxTime × edges)
空间复杂度	O(maxTime × n)

其中 n 是城市数量，edges 是边的数量。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目