Minimum Cost to Reach Destination in Time
Problem
There is a country of n cities numbered 0 to n-1, connected by bidirectional roads with travel times. passingFees[i] is the fee you pay each time you pass through city i (including start and end). Starting at city 0 at time 0, find the minimum total passing fee to reach city n-1 while the total travel time does not exceed maxTime. Return -1 if impossible.
maxTime = 10, edges = [[0,1,3],[1,2,3],[0,2,8]], passingFees = [5,1,2]7def min_cost(max_time, edges, passing_fees):
n = len(passing_fees)
INF = float("inf")
# dp[t][v] = min fee to be at city v using exactly t time
dp = [[INF] * n for _ in range(max_time + 1)]
dp[0][0] = passing_fees[0]
for t in range(max_time + 1):
for u, v, w in edges:
if t + w <= max_time:
if dp[t][u] + passing_fees[v] < dp[t + w][v]:
dp[t + w][v] = dp[t][u] + passing_fees[v]
if dp[t][v] + passing_fees[u] < dp[t + w][u]:
dp[t + w][u] = dp[t][v] + passing_fees[u]
ans = min(dp[t][n - 1] for t in range(max_time + 1))
return -1 if ans == INF else ansfunction minCost(maxTime, edges, passingFees) {
const n = passingFees.length, INF = Infinity;
const dp = Array.from({ length: maxTime + 1 }, () => new Array(n).fill(INF));
dp[0][0] = passingFees[0];
for (let t = 0; t <= maxTime; t++) {
for (const [u, v, w] of edges) {
if (t + w <= maxTime) {
if (dp[t][u] + passingFees[v] < dp[t + w][v]) dp[t + w][v] = dp[t][u] + passingFees[v];
if (dp[t][v] + passingFees[u] < dp[t + w][u]) dp[t + w][u] = dp[t][v] + passingFees[u];
}
}
}
let ans = INF;
for (let t = 0; t <= maxTime; t++) ans = Math.min(ans, dp[t][n - 1]);
return ans === INF ? -1 : ans;
}class Solution {
public int minCost(int maxTime, int[][] edges, int[] passingFees) {
int n = passingFees.length, INF = Integer.MAX_VALUE / 2;
int[][] dp = new int[maxTime + 1][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[0][0] = passingFees[0];
for (int t = 0; t <= maxTime; t++) {
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
if (t + w <= maxTime) {
if (dp[t][u] + passingFees[v] < dp[t + w][v]) dp[t + w][v] = dp[t][u] + passingFees[v];
if (dp[t][v] + passingFees[u] < dp[t + w][u]) dp[t + w][u] = dp[t][v] + passingFees[u];
}
}
}
int ans = INF;
for (int t = 0; t <= maxTime; t++) ans = Math.min(ans, dp[t][n - 1]);
return ans >= INF ? -1 : ans;
}
}int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
int n = passingFees.size(), INF = 1e9;
vector<vector<int>> dp(maxTime + 1, vector<int>(n, INF));
dp[0][0] = passingFees[0];
for (int t = 0; t <= maxTime; t++) {
for (auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
if (t + w <= maxTime) {
if (dp[t][u] + passingFees[v] < dp[t + w][v]) dp[t + w][v] = dp[t][u] + passingFees[v];
if (dp[t][v] + passingFees[u] < dp[t + w][u]) dp[t + w][u] = dp[t][v] + passingFees[u];
}
}
}
int ans = INF;
for (int t = 0; t <= maxTime; t++) ans = min(ans, dp[t][n - 1]);
return ans >= INF ? -1 : ans;
}Explanation
This is a shortest-path problem with a twist: the path must also fit inside a time budget. The clean way to handle two competing quantities (cost and time) is to make time part of the state. Let dp[t][v] be the cheapest fee to stand in city v having spent exactly t units of travel time.
We start paying the fee for city 0 the moment we are there: dp[0][0] = passingFees[0]; everything else begins at infinity (unreached).
We then process time levels in increasing order. From any reachable state dp[t][u] we can take an edge (u, v, w) if t + w still fits the budget, arriving at v at time t + w and paying passingFees[v]. Because roads are bidirectional we relax both directions. This forward relaxation is the dynamic-programming transition.
Since travel times are positive, time strictly increases along an edge, so processing t from small to large means a state is finalized before it is used — no cycles trap us. The answer is the minimum fee over all dp[t][n-1] for any time t within budget, or -1 if the destination is never reached.
Example: budget 10. Going 0 → 2 uses time 8 and costs 5 + 2 = 7; going 0 → 1 → 2 uses time 6 but costs 5 + 1 + 2 = 8. Both fit the budget, and the cheaper is 7.