力扣题解( 规定时间内到达终点的最小花费)

时间:2024-10-04 07:17:49

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 。旅行的 费用 为你经过的所有城市 通行费之和 (包括 起点和终点城市的通行费)。

给你 maxTimeedges 和 passingFees ,请你返回完成旅行的 最小费用 ,如果无法在 maxTime 分钟以内完成旅行,请你返回 -1 。

思路:

本题每一次选择城市都会影响到下一次城市的选择,因此可以采取动态递归的策略,正常设计数组dp,应该是dp[i][j]表示前i个城市用时在j的最小花费,但是由于本题是所有城市双向道路连接在一起,因此如果i从小到大遍历,后面结果变化可能会影响到前者,因此这么设计存在一定问题,需要更换dp[i][j]中i和j代表的含义,可以采用i表示花费的总时间,j表示到j城市,这样做的好处是i大的时候的变化都是由i小的时候得到的dp所决定的,而i大的dp[i][j]的变化又不会影响到之前的dp,因此方法是可行的。

具体的做法是i从0开始到maxtime,每次遍历所有的边,对于边【a,b】,dp[i][a]可以看成是dp[i-t][b]+passingFees[a],dp[i][b]可以看成是dp[i-t][a]+passingFees[b],其中t是a,b之间花费的时间。

最后答案就在dp[0][n-1]到dp[maxtime][n-1]之中取得最小值即可。

初始除了dp[0][0]=passingFees[0],其余全是INT_MAX即可。

class Solution {
public:
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
    int n=passingFees.size();
    vector<vector<int>>f(maxTime+1,vector<int>(n+1,0x3f3f3f3f));
    f[0][0]=passingFees[0];
    for(int i=1;i<=maxTime;i++)
    for(int j=0;j<edges.size();j++)
    {
        int a=edges[j][0],b=edges[j][1],tt=edges[j][2];
        if(tt<=i)
        f[i][a]=min(f[i][a],f[i-tt][b]+passingFees[a]),
        f[i][b]=min(f[i][b],f[i-tt][a]+passingFees[b]);
    }
    
    int ans=f[1][n-1];
    for(int i=2;i<=maxTime;i++)
    ans=min(ans,f[i][n-1]);
    if(ans>0x3f3f3f3f/2)return -1;
    return ans;
    }
};