Courier Toll Route with Dijkstra and One Pass
A courier service moves through a network of one-way roads. Each road is written as [from, to, travel, toll]. The normal cost of using that road is travel + toll.
The company gives the driver one special pass that can be used on at most one road during the whole trip. If the pass is used on a road, the toll for that road is ignored and only the travel cost is paid.
You are given the number of hubs, the list of roads, a start hub, and a destination hub. Return the minimum total delivery cost possible when the driver may use the pass zero or one time.
This version is more interesting than the basic shortest-path problem because arriving at the same hub can mean two different states. Reaching hub 5 without having used the pass is not the same as reaching hub 5 after the pass has already been spent. Those situations lead to different future choices.
That is why the solution needs Dijkstra with an expanded state space. The algorithm is still about shortest paths, but now the state includes both the current node and whether the one-use pass has already been consumed.
Example Input & Output
Using the pass on road 0 -> 2 gives the cheapest total cost of 8.
The best route spends the pass on one of the chain roads and beats the direct road cost.
There is no directed path from the start hub to the destination hub.
Algorithm Flow
Solution Approach
This is a classic example of running Dijkstra on a graph with extra state. The current hub alone is not enough to describe where you are in the problem, because the remaining usefulness of the toll pass changes what costs are possible next.
A clean design is to keep dist[node][used], where used is 0 if the pass is still available and 1 if it has already been used. That means the same node may have two different shortest known costs, one for each pass state.
When you explore a road [u, v, travel, toll], you have two possible relaxations:
1. Travel normally and pay travel + toll.
2. If the pass is still unused, spend it here and move to the state where it becomes used, paying only travel.
In Java, the priority queue can carry triples like {cost, node, used}. Then each pop gives you both the position and the pass status for that route state.
The heart of the logic looks like this:
This is exactly why the problem is medium level. The shortest-path algorithm itself is familiar, but the model becomes slightly larger because each node has multiple legal modes. Once that state is represented correctly, the rest of Dijkstra works in the usual way.
The runtime is roughly O((n + m) log (2n)), which is still the same practical order as standard Dijkstra, just on twice as many states.
Best Answers
import java.util.*;
class Solution {
public int courier_toll_route_with_dijkstra(int n, int[][] roads, int start, int destination) {
List<int[]>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] road : roads) {
graph[road[0]].add(new int[]{road[1], road[2], road[3]});
}
int[][] dist = new int[n][2];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
dist[start][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, start, 0});
while (!pq.isEmpty()) {
int[] state = pq.poll();
int cost = state[0];
int node = state[1];
int used = state[2];
if (cost != dist[node][used]) {
continue;
}
if (node == destination) {
return cost;
}
for (int[] edge : graph[node]) {
int next = edge[0];
int travel = edge[1];
int toll = edge[2];
int keepPass = cost + travel + toll;
if (keepPass < dist[next][used]) {
dist[next][used] = keepPass;
pq.offer(new int[]{keepPass, next, used});
}
if (used == 0) {
int spendPass = cost + travel;
if (spendPass < dist[next][1]) {
dist[next][1] = spendPass;
pq.offer(new int[]{spendPass, next, 1});
}
}
}
}
return -1;
}
}Comments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this Challenge.