Problem

You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.

You are given an integer n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.

Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 10^9 + 7.

Examples

Example 1:

graph TD
    A(0)
    B(1)
    C(2)
    D(3)
    E(4)
    F(5)
    G(6)

	A ---|5| E
	A ---|7| G
	A ---|2| B
    B ---|3| C
    B ---|3| D
    G ---|3| D
    D ---|1| F
    G ---|1| F
    C ---|1| F
    E ---|2| G
  
1
2
3
4
5
6
7
8

Input: n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6

Example 2:

1
2
3

Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.

Constraints:

  • 1 <= n <= 200
  • n - 1 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 3
  • 0 <= ui, vi <= n - 1
  • 1 <= timei <= 10^9
  • ui != vi
  • There is at most one road connecting any two intersections.
  • You can reach any intersection from any other intersection.

Solution

Method 1 - Using Dijkstra Algorithm

To solve this problem, we aim to compute the number of ways to reach intersection n-1 from 0 using the shortest time possible. This involves using Dijkstra’s algorithm to find the shortest path and counting the number of paths that result in the shortest time.

Approach

  1. Graph Representation: Represent the city as an adjacency list where each node points to its neighbours with the road times.
  2. Shortest Path Calculation: Implement Dijkstra’s algorithm to calculate the shortest path from intersection 0 to n-1.
  3. Counting Paths: During the execution of Dijkstra’s algorithm, maintain two arrays:
    • dist: Stores the shortest distance from 0 to each node.
    • ways: Tracks how many ways we can reach each node using the shortest time.
  4. Modulo Constraint: As the problem requires, return the count modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
    public int countPaths(int n, int[][] roads) {
        List<List<int[]>> graph = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] road : roads) {
            int u = road[0], v = road[1], w = road[2];
            graph.get(u).add(new int[]{v, w});
            graph.get(v).add(new int[]{u, w});
        }
        
        // Dijkstra's algorithm components
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0])); // Min-heap
        pq.offer(new long[]{0, 0}); // {distance, node}
        
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;
        
        int[] ways = new int[n];
        ways[0] = 1;

        final int MOD = 1_000_000_007;
        
        while (!pq.isEmpty()) {
            long[] curr = pq.poll();
            long time = curr[0];
            int node = (int) curr[1];
            
            if (time > dist[node]) {
                continue;
            }
            
            for (int[] nei : graph.get(node)) {
                int nextNode = nei[0], travelTime = nei[1];
                long newTime = time + travelTime;
                
                // Shorter path found
                if (newTime < dist[nextNode]) {
                    dist[nextNode] = newTime;
                    pq.offer(new long[]{newTime, nextNode});
                    ways[nextNode] = ways[node];
                }
                // Equal path length found -> Accumulate ways
                else if (newTime == dist[nextNode]) {
                    ways[nextNode] = (ways[nextNode] + ways[node]) % MOD;
                }
            }
        }
        
        return ways[n - 1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # Build graph as adjacency list
        graph = [[] for _ in range(n)]
        for u, v, time in roads:
            graph[u].append((v, time))
            graph[v].append((u, time))
        
        # Initialise distances and ways arrays
        dist = [float('inf')] * n
        ways = [0] * n
        dist[0] = 0
        ways[0] = 1
        
        # Priority queue for Dijkstra's algorithm
        pq = [(0, 0)]  # (distance, node)
        while pq:
            time, node = heapq.heappop(pq)
            
            # Skip outdated distance records
            if time > dist[node]:
                continue
            
            # Process neighbours
            for neighbor, travel_time in graph[node]:
                new_time = time + travel_time
                
                # Found a shorter path
                if new_time < dist[neighbor]:
                    dist[neighbor] = new_time  # Update the shortest distance
                    ways[neighbor] = ways[node]  # Inherit the number of ways
                    heapq.heappush(pq, (new_time, neighbor))
                
                # Found an alternate path with the same shortest distance
                elif new_time == dist[neighbor]:
                    ways[neighbor] = (ways[neighbor] + ways[node]) % MOD  # Accumulate the number of ways
        
        # Return number of ways to reach the last node
        return ways[n - 1]

Complexity

  • ⏰ Time complexity: O((n + roads.size()) * log(n)).
    • Graph Construction: O(n + roads.size()), where roads.size() is the number of roads.
    • Dijkstra’s Algorithm: O((n + roads.size()) * log(n)) using a priority queue.
  • 🧺 Space complexity: O(n + roads.size())
    • Graph Storage: O(n + roads.size()).
    • Extra Arrays (dist and ways): O(n).