Cheapest Route to Every Town With Road Tolls
Solve this ProblemYou are given a network of towns connected by two-way roads, each with a positive toll, as a symmetric weight matrix. Starting from one town, find the smallest total toll to every other town, or -1 for towns that cannot be reached.
With only positive tolls, the town with the smallest known toll can never be reached more cheaply later: that is the greedy idea behind Dijkstra's algorithm.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 8 towns numbered 0 … n-1; weights is a symmetric n × n matrix: weights[u][v] = 0 means no road between u and v, and weights[u][v] = w (1 ≤ w ≤ 20) means a two-way road with toll w - ◆
weights[u][u] = 0; all tolls are positive - ◆
0 ≤ src < n is the starting town - ◆
Return an array where entry i is the smallest total toll on a route from src to town i, or -1 if town i cannot be reached
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Route and Keep the Cheapest for Each Town
BruteExplore every simple route (one that never visits a town twice) that starts at the source: at each town follow every road to a town not yet on the current route, adding tolls as you go. Whenever a town is reached, compare the toll of the current route with the best found for that town so far. This tries every possible route, of which there can be about n! — fine for a handful of towns, hopeless for more.
O(n!) routesO(n)1class Solution {
2 private void explore(int[][] weights, int u, int cost, boolean[] onPath, int[] best) {
3 best[u] = Math.min(best[u], cost);
4 onPath[u] = true;
5 for (int v = 0; v < weights.length; v++) {
6 if (weights[u][v] > 0 && !onPath[v]) {
7 explore(weights, v, cost + weights[u][v], onPath, best);
8 }
9 }
10 onPath[u] = false;
11 }
12
13 public int[] cheapestRoutes(int[][] weights, int src) {
14 int n = weights.length;
15 int INF = Integer.MAX_VALUE;
16 int[] best = new int[n];
17 Arrays.fill(best, INF);
18 explore(weights, src, 0, new boolean[n], best);
19 for (int i = 0; i < n; i++) {
20 if (best[i] == INF) best[i] = -1;
21 }
22 return best;
23 }
24}Optimal — Dijkstra’s Algorithm
OptimalKeep the best known toll for every town (infinity, except 0 for the source). Repeatedly pick the unfinished town with the smallest known toll — since all tolls are positive, no other route can reach it more cheaply, so its toll is final — mark it finished, and offer each neighbour the toll of this town plus the road toll, keeping it if it is smaller. After n rounds every reachable town is final. With a matrix and a linear scan for the minimum this is O(n²) (with adjacency lists and a heap it is O((n + E) log n)).
O(n²)O(n)1class Solution {
2 public int[] cheapestRoutes(int[][] weights, int src) {
3 int n = weights.length;
4 int INF = Integer.MAX_VALUE;
5 int[] dist = new int[n];
6 Arrays.fill(dist, INF);
7 dist[src] = 0;
8 boolean[] done = new boolean[n];
9 for (int round = 0; round < n; round++) {
10 int u = -1;
11 for (int i = 0; i < n; i++) {
12 if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
13 }
14 if (u == -1 || dist[u] == INF) break;
15 done[u] = true;
16 for (int v = 0; v < n; v++) {
17 if (weights[u][v] > 0 && dist[u] + weights[u][v] < dist[v]) {
18 dist[v] = dist[u] + weights[u][v];
19 }
20 }
21 }
22 for (int i = 0; i < n; i++) {
23 if (dist[i] == INF) dist[i] = -1;
24 }
25 return dist;
26 }
27}