✔️ DP + Dijkstra | Python | C++ | Java | JS | C# | Go | Rust | Kotlin
SUPPORT BY UPVOTING THE POST ⬆️IntuitionThis problem combines the shortest path algorithm with counting the number of ways to reach a destination using the shor
# SUPPORT BY UPVOTING THE POST ⬆️

# Intuition
This problem combines the shortest path algorithm with counting the number of ways to reach a destination using the shortest path. We use **Dijkstra's algorithm** to find the shortest paths and simultaneously count how many different ways we can reach each node with the current shortest distance.

# Approach
1. **Build the Graph:** Create an adjacency list representation of the graph where for each node, we store its neighbors and the time to reach them.
2. **Initialize:**
    - Create a `dist` array to store the shortest distance to each node (initially infinity, except dist[0] = 0)
    - Create a `ways` array to count the number of ways to reach each node via the shortest path (initially ways[0] = 1, others = 0)
3. **Dijkstra's Algorithm with DP:**
    - Use a priority queue to explore nodes in order of increasing distance
    - For each node, look at all its neighbors
    - If we find a shorter path to a neighbor, update its distance and reset its count of ways
    - If we find a path of equal length, add the current node's count to the neighbor's count
4. **Result:** After the algorithm completes, `ways[n-1]` contains the number of shortest paths from node 0 to node n-1.

The **dynamic programming** aspect comes from how we update the `ways` array. For each node, the number of ways to reach it is the sum of the ways to reach all its predecessors in the shortest path.

# Complexity
- Time Complexity: `O(E log V)`, where `E` is the number of edges (roads) and `V` is the number of vertices (intersections).

- Space complexity: `O(V + E)`.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for u, v, time in roads:
            graph[u].append((v, time))
            graph[v].append((u, time))
            
        dist = [float('inf')] * n
        ways = [0] * n
        
        dist[0] = 0
        ways[0] = 1
        
        pq = [(0, 0)]
        
        MOD = 10**9 + 7
        
        # Dijkstra's algorithm
        while pq:
            d, node = heapq.heappop(pq)
            
            if d > dist[node]:
                continue
                
            for neighbor, time in graph[node]:
                if dist[node] + time < dist[neighbor]:
                    dist[neighbor] = dist[node] + time
                    ways[neighbor] = ways[node]
                    heapq.heappush(pq, (dist[neighbor], neighbor))
                elif dist[node] + time == dist[neighbor]:
                    ways[neighbor] = (ways[neighbor] + ways[node]) % MOD
        
        return ways[n-1]
```
```cpp []
class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int, int>>> graph(n);
        for (const auto& road : roads) {
            int u = road[0], v = road[1], time = road[2];
            graph[u].emplace_back(v, time);
            graph[v].emplace_back(u, time);
        }

        vector<long long> dist(n, LLONG_MAX);
        vector<int> ways(n, 0);

        dist[0] = 0;
        ways[0] = 1;

        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
        pq.emplace(0, 0);

        const int MOD = 1e9 + 7;

        while (!pq.empty()) {
            auto [d, node] = pq.top();
            pq.pop();

            if (d > dist[node]) continue;

            for (const auto& [neighbor, time] : graph[node]) {
                if (dist[node] + time < dist[neighbor]) {
                    dist[neighbor] = dist[node] + time;
                    ways[neighbor] = ways[node];
                    pq.emplace(dist[neighbor], neighbor);
                } else if (dist[node] + time == dist[neighbor]) {
                    ways[neighbor] = (ways[neighbor] + ways[node]) % MOD;
                }
            }
        }

        return ways[n - 1];
    }
};
```
```java []
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], time = road[2];
            graph.get(u).add(new int[]{v, time});
            graph.get(v).add(new int[]{u, time});
        }

        long[] dist = new long[n];
        int[] ways = new int[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;
        ways[0] = 1;

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, 0});

        int MOD = 1_000_000_007;

        while (!pq.isEmpty()) {
            long[] curr = pq.poll();
            long d = curr[0];
            int node = (int) curr[1];

            if (d > dist[node]) continue;

            for (int[] neighbor : graph.get(node)) {
                int nextNode = neighbor[0];
                int time = neighbor[1];

                if (dist[node] + time < dist[nextNode]) {
                    dist[nextNode] = dist[node] + time;
                    ways[nextNode] = ways[node];
                    pq.offer(new long[]{dist[nextNode], nextNode});
                } else if (dist[node] + time == dist[nextNode]) {
                    ways[nextNode] = (ways[nextNode] + ways[node]) % MOD;
                }
            }
        }

        return ways[n - 1];
    }
}
```
```javascript []
var countPaths = function(n, roads) {
    const graph = Array.from({ length: n }, () => []);
    
    for (const [u, v, time] of roads) {
        graph[u].push([v, time]);
        graph[v].push([u, time]);
    }

    const dist = Array(n).fill(Infinity);
    const ways = Array(n).fill(0);
    
    dist[0] = 0;
    ways[0] = 1;
    
    const pq = new MinHeap();
    pq.push([0, 0]);

    const MOD = 1e9 + 7;

    while (!pq.isEmpty()) {
        const [d, node] = pq.pop();

        if (d > dist[node]) continue;

        for (const [neighbor, time] of graph[node]) {
            if (dist[node] + time < dist[neighbor]) {
                dist[neighbor] = dist[node] + time;
                ways[neighbor] = ways[node];
                pq.push([dist[neighbor], neighbor]);
            } else if (dist[node] + time === dist[neighbor]) {
                ways[neighbor] = (ways[neighbor] + ways[node]) % MOD;
            }
        }
    }

    return ways[n - 1];
};

class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this._heapifyUp();
    }

    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapifyDown();
        return top;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    _heapifyUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx][0] <= this.heap[idx][0]) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }

    _heapifyDown() {
        let idx = 0;
        while (2 * idx + 1 < this.heap.length) {
            let leftIdx = 2 * idx + 1, rightIdx = 2 * idx + 2;
            let smallest = leftIdx;
            if (rightIdx < this.heap.length && this.heap[rightIdx][0] < this.heap[leftIdx][0]) {
                smallest = rightIdx;
            }
            if (this.heap[idx][0] <= this.heap[smallest][0]) break;
            [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
            idx = smallest;
        }
    }
}
```
```csharp []
public class Solution {
    public int CountPaths(int n, int[][] roads) {
        List<(int, int)>[] graph = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<(int, int)>();

        foreach (var road in roads) {
            int u = road[0], v = road[1], time = road[2];
            graph[u].Add((v, time));
            graph[v].Add((u, time));
        }

        long[] dist = new long[n];
        int[] ways = new int[n];
        Array.Fill(dist, long.MaxValue);
        Array.Fill(ways, 0);

        dist[0] = 0;
        ways[0] = 1;
        int MOD = 1_000_000_007;

        PriorityQueue<(long d, int v), (long d, int v)> pq = new();
        pq.Enqueue((0, 0), (0, 0));

        while (pq.Count > 0) {
            var (d, node) = pq.Dequeue();
            if (d > dist[node])
            {
                continue;
            }
            
            foreach (var (neighbor, time) in graph[node]) {
                if (dist[node] + time < dist[neighbor]) {
                    dist[neighbor] = dist[node] + time;
                    ways[neighbor] = ways[node];
                    pq.Enqueue((dist[neighbor], neighbor), (dist[neighbor], neighbor));
                } else if (dist[node] + time == dist[neighbor]) {
                    ways[neighbor] = (ways[neighbor] + ways[node]) % MOD;
                }
            }
        }

        return ways[n - 1];
    }
}
```
```go []
func countPaths(n int, roads [][]int) int {
    const MOD = 1_000_000_007

	graph := make([][][2]int, n)

	for _, road := range roads {
		u, v, time := road[0], road[1], road[2]
		graph[u] = append(graph[u], [2]int{v, time})
		graph[v] = append(graph[v], [2]int{u, time})
	}

	dist := make([]int, n)
	ways := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt64
	}
	dist[0] = 0
	ways[0] = 1

	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, &Item{node: 0, cost: 0})

	for pq.Len() > 0 {
		cur := heap.Pop(pq).(*Item)

		if cur.cost > dist[cur.node] {
			continue
		}

		for _, neighbor := range graph[cur.node] {
			nextNode, time := neighbor[0], neighbor[1]
			newDist := cur.cost + time

			if newDist < dist[nextNode] {
				dist[nextNode] = newDist
				ways[nextNode] = ways[cur.node]
				heap.Push(pq, &Item{node: nextNode, cost: newDist})
			} else if newDist == dist[nextNode] {
				ways[nextNode] = (ways[nextNode] + ways[cur.node]) % MOD
			}
		}
	}

	return ways[n-1]
}

// Priority Queue Implementation
type Item struct {
	node int
	cost int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].cost < pq[j].cost }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(*Item))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}
```
```rust []
use std::collections::BinaryHeap;
use std::cmp::Reverse;

const MOD: i32 = 1_000_000_007;

impl Solution {
    pub fn count_paths(n: i32, roads: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut graph = vec![vec![]; n];

        for road in &roads {
            let (u, v, time) = (road[0] as usize, road[1] as usize, road[2]);
            graph[u].push((v, time));
            graph[v].push((u, time));
        }

        let mut dist = vec![i64::MAX; n];
        let mut ways = vec![0; n];

        dist[0] = 0;
        ways[0] = 1;

        let mut pq = BinaryHeap::new();
        pq.push(Reverse((0, 0)));

        while let Some(Reverse((cur_dist, node))) = pq.pop() {
            if cur_dist > dist[node] {
                continue;
            }

            for &(neighbor, time) in &graph[node] {
                let new_dist = cur_dist + time as i64;

                if new_dist < dist[neighbor] {
                    dist[neighbor] = new_dist;
                    ways[neighbor] = ways[node];
                    pq.push(Reverse((new_dist, neighbor)));
                } else if new_dist == dist[neighbor] {
                    ways[neighbor] = (ways[neighbor] + ways[node]) % MOD;
                }
            }
        }

        ways[n - 1]
    }
}
```
```kotlin []
class Solution {
    fun countPaths(n: Int, roads: Array<IntArray>): Int {
        val graph = Array(n) { mutableListOf<Pair<Int, Int>>() }

        for (road in roads) {
            val (u, v, time) = road
            graph[u].add(Pair(v, time))
            graph[v].add(Pair(u, time))
        }

        val dist = LongArray(n) { Long.MAX_VALUE }
        val ways = IntArray(n) { 0 }
        val MOD = 1_000_000_007

        dist[0] = 0
        ways[0] = 1

        val pq = PriorityQueue(compareBy<Pair<Long, Int>> { it.first })
        pq.add(Pair(0L, 0))

        while (pq.isNotEmpty()) {
            val (curDist, node) = pq.poll()

            if (curDist > dist[node]) continue

            for ((neighbor, time) in graph[node]) {
                val newDist = curDist + time

                if (newDist < dist[neighbor]) {
                    dist[neighbor] = newDist
                    ways[neighbor] = ways[node]
                    pq.add(Pair(newDist, neighbor))
                } else if (newDist == dist[neighbor]) {
                    ways[neighbor] = (ways[neighbor] + ways[node]) % MOD
                }
            }
        }

        return ways[n - 1]
    }
}
```

---

![upvote.png](https://assets.leetcode.com/users/images/c0930914-2118-4427-8fe3-aebe23df84b6_1742691313.8578413.png)

['Dynamic Programming', 'Shortest Path', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'Kotlin', 'JavaScript', 'C#']