DAY 28
0
Software Development

## 11.8 更多的 Leetcode

### Leetcode 1928. Minimum Cost to Reach Destination in Time

https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/

``````class Solution {
public:
int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
int n = passingFees.size();
int m = edges.size();
int dp[1005][1005];
memset(dp, -1, sizeof(dp));
for (int i = 0; i < m; i++) {
}

dp[0][0] = passingFees[0];
for (int t = 0; t <= maxTime; t++) {
for (int x = 0; x < n; x++) {
if (t > 0 && dp[t-1][x] != -1 && (dp[t][x] == -1 || dp[t][x] > dp[t-1][x])) dp[t][x] = dp[t-1][x];
if (dp[t][x] != -1 && (t == 0 || dp[t][x] != dp[t-1][x])) {
for (int i : adj[x]) {
int y = edges[i][0] + edges[i][1] - x;
int z = t + edges[i][2];
int c = dp[t][x] + passingFees[y];
if (z <= maxTime && (dp[z][y] == -1 || dp[z][y] > c)) {
dp[z][y] = c;
}
}
}
}
}

int minCost = -1;
for (int t = 0; t <= maxTime; t++) {
if (dp[t][n-1] != -1 && (minCost == -1 || minCost > dp[t][n-1]))
minCost = dp[t][n-1];
}
return minCost;

}
};
``````

### 1 則留言

0
juck30808
iT邦新手 3 級 ‧ 2021-10-12 18:34:29