You are given a network of cities connected by roads, where each road has a time and a cost. Your goal is to travel from city 0 to city n - 1 (where n is the total number of cities) in at most maxTime units of time, while minimizing the total cost spent on the journey.
n: Number of cities, labeled from 0 to n-1.edges: Each edge is represented as [u, v, time, cost], indicating a road between city u and v that takes time to traverse and costs cost.maxTime: The maximum total time allowed for the journey.
You can revisit cities and edges multiple times. Your task is to find the minimum cost to reach city n-1 from city 0 within maxTime. If it's impossible, return -1.
At first glance, this problem looks similar to the shortest path problem, like Dijkstra's algorithm. However, there are two weights on each edge: time and cost, and we must minimize cost while keeping total time within maxTime. Unlike traditional shortest path, we care about two dimensions for each path.
A brute-force approach would try all possible paths from 0 to n-1, tracking their total time and cost, and picking the lowest cost among those within maxTime. This is clearly infeasible for large graphs due to the exponential number of paths.
The key insight is to optimize by tracking, for every city and every possible time up to maxTime, the minimum cost needed to reach that city in that time. This is similar to dynamic programming or a modified Dijkstra's algorithm, where the state includes both the current city and the total time used so far.
We'll use a modified Dijkstra's algorithm with a priority queue (min-heap) to always expand the state with the lowest cost so far. Each state in the queue will be a tuple: (current_cost, current_time, current_city).
edges input for quick lookups of neighboring cities and their corresponding time and cost.
min_cost[city][time] to record the minimum cost to reach city in time. This avoids revisiting worse states.
(0, 0, 0) (cost, time, city). At each step, pop the state with the lowest cost. For each neighbor, if traveling there does not exceed maxTime and the new cost is lower than any previously found for that city and time, push the new state to the queue.
current_city == n-1, return the current_cost — this is the minimum cost to reach the destination within the allowed time.
maxTime, return -1.
This approach ensures we always explore the lowest-cost paths first, and never revisit a state with a higher cost for the same or greater time.
Suppose n = 3, edges = [[0,1,10,100],[1,2,10,100],[0,2,30,500]], and maxTime = 20.
0 with cost=0 and time=0.0:
1: time=10, cost=100.2: time=30 (exceeds maxTime, skip).1:
2: time=10+10=20, cost=100+100=200 (within maxTime).2 in time=20 with cost=200.0 to 2 is too slow (time = 30), so the answer is 200.The algorithm explores states in order of increasing cost, always pruning worse options.
O(E * maxTime), where E is the number of edges. For each city and each possible time value up to maxTime, we may update the state once per edge.
O(N * maxTime) for the min_cost table, where N is the number of cities.
The use of a priority queue ensures we process the most promising states first, and the 2D state table prevents redundant work.
This problem is a variant of the shortest path problem with dual constraints: minimizing cost and staying within a maxTime limit. By extending Dijkstra's algorithm to include time as part of the state, we efficiently find the minimum cost path that satisfies the time constraint. The key insight is to track the best cost for each city at each possible time, ensuring optimality without redundant exploration. This makes the solution both elegant and efficient for practical input sizes.
import heapq
from collections import defaultdict
class Solution:
def minCost(self, maxTime, edges, passingFees):
n = len(passingFees)
graph = defaultdict(list)
for u, v, time, cost in edges:
graph[u].append((v, time, cost))
graph[v].append((u, time, cost))
# min_cost[city][time] = min cost to reach city in <= time
min_cost = [ [float('inf')] * (maxTime + 1) for _ in range(n) ]
min_cost[0][0] = passingFees[0]
heap = [(passingFees[0], 0, 0)] # (cost, time, city)
while heap:
cost, time, city = heapq.heappop(heap)
if city == n - 1:
return cost
for nei, t, c in graph[city]:
next_time = time + t
if next_time > maxTime:
continue
next_cost = cost + passingFees[nei]
if min_cost[nei][next_time] > next_cost:
min_cost[nei][next_time] = next_cost
heapq.heappush(heap, (next_cost, next_time, nei))
return -1
#include <vector>
#include <queue>
#include <climits>
using namespace std;
class Solution {
public:
int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
int n = passingFees.size();
vector<vector<vector<int>>> graph(n);
for (auto& e : edges) {
int u = e[0], v = e[1], t = e[2], c = e[3];
graph[u].push_back({v, t, c});
graph[v].push_back({u, t, c});
}
vector<vector<int>> min_cost(n, vector<int>(maxTime + 1, INT_MAX));
min_cost[0][0] = passingFees[0];
using T = tuple<int, int, int>; // cost, time, city
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({passingFees[0], 0, 0});
while (!pq.empty()) {
auto [cost, time, city] = pq.top(); pq.pop();
if (city == n - 1) return cost;
for (auto& nei : graph[city]) {
int v = nei[0], t = nei[1], c = nei[2];
int next_time = time + t;
if (next_time > maxTime) continue;
int next_cost = cost + passingFees[v];
if (min_cost[v][next_time] > next_cost) {
min_cost[v][next_time] = next_cost;
pq.push({next_cost, next_time, v});
}
}
}
return -1;
}
};
import java.util.*;
class Solution {
public int minCost(int maxTime, int[][] edges, int[] passingFees) {
int n = passingFees.length;
List<int[]>[] graph = new List[n];
for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>();
for (int[] e : edges) {
graph[e[0]].add(new int[]{e[1], e[2], e[3]});
graph[e[1]].add(new int[]{e[0], e[2], e[3]});
}
int[][] minCost = new int[n][maxTime + 1];
for (int[] arr : minCost) Arrays.fill(arr, Integer.MAX_VALUE);
minCost[0][0] = passingFees[0];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{passingFees[0], 0, 0}); // cost, time, city
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int cost = curr[0], time = curr[1], city = curr[2];
if (city == n - 1) return cost;
for (int[] nei : graph[city]) {
int v = nei[0], t = nei[1], c = nei[2];
int nextTime = time + t;
if (nextTime > maxTime) continue;
int nextCost = cost + passingFees[v];
if (minCost[v][nextTime] > nextCost) {
minCost[v][nextTime] = nextCost;
pq.offer(new int[]{nextCost, nextTime, v});
}
}
}
return -1;
}
}
/**
* @param {number} maxTime
* @param {number[][]} edges
* @param {number[]} passingFees
* @return {number}
*/
var minCost = function(maxTime, edges, passingFees) {
const n = passingFees.length;
const graph = Array.from({length: n}, () => []);
for (const [u, v, t, c] of edges) {
graph[u].push([v, t, c]);
graph[v].push([u, t, c]);
}
const minCost = Array.from({length: n}, () => Array(maxTime + 1).fill(Infinity));
minCost[0][0] = passingFees[0];
// [cost, time, city]
const heap = [[passingFees[0], 0, 0]];
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]);
const [cost, time, city] = heap.shift();
if (city === n - 1) return cost;
for (const [nei, t, c] of graph[city]) {
const nextTime = time + t;
if (nextTime > maxTime) continue;
const nextCost = cost + passingFees[nei];
if (minCost[nei][nextTime] > nextCost) {
minCost[nei][nextTime] = nextCost;
heap.push([nextCost, nextTime, nei]);
}
}
}
return -1;
};