Count the Cheapest Routes Between Two Cities

Implement countCheapestRoutes

You 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.

Example 1:

Input: roads = [[0,2,2,0,0,0],[2,0,1,3,0,0],[2,1,0,3,0,0],[0,3,3,0,2,5],[0,0,0,2,0,3],[0,0,0,5,3,0]]

Output: 4

Example 2:

Input: roads = [[0,4],[4,0]]

Output: 1

Example 3:

Input: roads = [[0,0],[0,0]]

Output: 0

+ 15 hidden test cases run on Submit.

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)

roads =

[[0,2,2,0,0,0], [2,0,1,3,0,0], [2,1,0,3,0,0], [0,3,3,0,2,5], [0,0,0,2,0,3], [0,0,0,5,3,0]]