Count the Cheapest Routes Between Two Cities
Solve this ProblemYou are given a road network of n cities as a symmetric matrix of travel times (0 means no road). Count how many different routes lead from city 0 to city n-1 in the minimum possible total time. Return the count modulo 1 000 000 007, or 0 if city n-1 is unreachable.
Dijkstra's algorithm finds the shortest times; keeping a counter next to each time lets it count the shortest routes at the same time.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ n ≤ 8 cities numbered 0 … n-1; roads is a symmetric n × n matrix: roads[u][v] = 0 means no road between u and v, and roads[u][v] = t (1 ≤ t ≤ 20) means a two-way road that takes t minutes - ◆
roads[u][u] = 0; all times are positive - ◆
You travel from city 0 to city n-1; two routes are different when they visit different sequences of cities - ◆
Return the number of routes that take the minimum possible total time, modulo 1 000 000 007 (0 if city n-1 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 — Enumerate Every Route and Count the Cheapest
BruteExplore every simple route from city 0 (never visiting a city twice), adding up the times. Whenever city n-1 is reached, compare the total with the best so far: a smaller total resets the counter to 1, an equal total adds 1. With positive times the fastest routes never repeat a city, so this counts exactly the fastest routes. The number of routes grows explosively, about n!.
O(n!)O(n)1class Solution {
2 private int best;
3 private int ways;
4
5 private void explore(int[][] roads, int u, int cost, boolean[] onPath) {
6 int n = roads.length;
7 if (u == n - 1) {
8 if (cost < best) {
9 best = cost;
10 ways = 1;
11 } else if (cost == best) {
12 ways++;
13 }
14 return;
15 }
16 onPath[u] = true;
17 for (int v = 0; v < n; v++) {
18 if (roads[u][v] > 0 && !onPath[v]) {
19 explore(roads, v, cost + roads[u][v], onPath);
20 }
21 }
22 onPath[u] = false;
23 }
24
25 public int countCheapestRoutes(int[][] roads) {
26 best = Integer.MAX_VALUE;
27 ways = 0;
28 explore(roads, 0, 0, new boolean[roads.length]);
29 return ways;
30 }
31}Optimal — Dijkstra With a Route Counter
OptimalRun Dijkstra's algorithm from city 0 and keep, next to each city's shortest time, the NUMBER of fastest routes reaching it (1 for the start). When a road from u offers v a strictly smaller time, v's counter is REPLACED by u's counter (all the older routes are slower). When the offer is EQUAL to v's current time, u's routes are added to v's counter (modulo 1 000 000 007). Because u is final when it is processed, its counter is complete. The answer is the counter of city n-1.
O(n²)O(n)1class Solution {
2 public int countCheapestRoutes(int[][] roads) {
3 int n = roads.length;
4 int INF = Integer.MAX_VALUE;
5 long MOD = 1_000_000_007L;
6 int[] dist = new int[n];
7 long[] ways = new long[n];
8 boolean[] done = new boolean[n];
9 Arrays.fill(dist, INF);
10 dist[0] = 0;
11 ways[0] = 1;
12 for (int round = 0; round < n; round++) {
13 int u = -1;
14 for (int i = 0; i < n; i++) {
15 if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
16 }
17 if (u == -1 || dist[u] == INF) break;
18 done[u] = true;
19 for (int v = 0; v < n; v++) {
20 if (roads[u][v] == 0) continue;
21 int candidate = dist[u] + roads[u][v];
22 if (candidate < dist[v]) {
23 dist[v] = candidate;
24 ways[v] = ways[u];
25 } else if (candidate == dist[v]) {
26 ways[v] = (ways[v] + ways[u]) % MOD;
27 }
28 }
29 }
30 return dist[n - 1] == INF ? 0 : (int) ways[n - 1];
31 }
32}