✅🚀easy Dijkstra+graph+friendly with explain code in all languages
guys please upvote for support 😊🌟 Intuition and Approach — Shortest Path + Counting Paths1.🏙️ Problem:

We need to find the number of shortest paths from the st
 # *guys please upvote for support 😊*
# 🌟 Intuition and Approach — Shortest Path + Counting Paths
 # 1.🏙️ **Problem:**
- ###### We need to find the number of shortest paths from the starting node (0) to the destination node (n-1) in a weighted graph.

# 2. 🛣️ Graph Representation:

- ###### The graph is represented using an adjacency list (adj), where each node connects to its neighbors along with the travel time (edge weight).

# 3.⏳ Dijkstra's Algorithm:

- ###### We use Dijkstra’s algorithm to find the shortest paths.

- ###### Maintain shortesttime[] to store the minimum time to reach each node.

- ###### Use a priority queue (pq) to explore nodes based on the smallest travel time.

# 4.🔢 Counting Paths:

- ###### Maintain cnt[] to track the number of ways to reach each node via the shortest path.

- ###### If a shorter path is found, update the time and reset the count for that node.

- ###### If an equally short path is found, add the number of paths from the current node to the neighbor.

# 5.🔁 Process:

- ###### Explore neighbors of each node from the priority queue.

- ###### If a shorter path to a neighbor is found, update both the time and count.

- ###### If an equally short path is found, accumulate the count.

# 6.🎯 Result:

- ###### The result is stored in cnt[n-1], representing the number of shortest paths to the last node.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    O((N+E)logN)

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

# Code
```cpp []
class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        int mod=1e9+7;
        vector<vector<pair<int,int>>>adj(n);
        for(auto r:roads){
            adj[r[0]].push_back({r[1],r[2]});
            adj[r[1]].push_back({r[0],r[2]});
        }
        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>>pq;
        vector<long long>shortesttime(n,LLONG_MAX);
        vector<int>cnt(n,0);
        shortesttime[0]=0;
        cnt[0]=1;
        pq.push({0,0});
        while(!pq.empty()){
            long long time=pq.top().first;
            int node=pq.top().second;
            pq.pop();
            if(time>shortesttime[node])continue;
            for(auto [nbr,rtime]:adj[node]){
                if(time+rtime<shortesttime[nbr]){
                    shortesttime[nbr]=time+rtime;
                    cnt[nbr]=cnt[node];
                    pq.push({shortesttime[nbr],nbr});
                }
                else if(time+rtime==shortesttime[nbr]){
                    cnt[nbr]=(cnt[nbr]+cnt[node])%mod;
                }
            }
        }
        return cnt[n-1];
    }
};
```
```python []
import heapq
from collections import defaultdict
import sys

def countPaths(n, roads):
    mod = 10**9 + 7
    adj = defaultdict(list)
    for u, v, t in roads:
        adj[u].append((v, t))
        adj[v].append((u, t))

    shortesttime = [sys.maxsize] * n
    cnt = [0] * n
    pq = [(0, 0)]  # (time, node)
    
    shortesttime[0] = 0
    cnt[0] = 1

    while pq:
        time, node = heapq.heappop(pq)

        if time > shortesttime[node]:
            continue

        for nbr, rtime in adj[node]:
            if time + rtime < shortesttime[nbr]:
                shortesttime[nbr] = time + rtime
                cnt[nbr] = cnt[node]
                heapq.heappush(pq, (shortesttime[nbr], nbr))
            elif time + rtime == shortesttime[nbr]:
                cnt[nbr] = (cnt[nbr] + cnt[node]) % mod

    return cnt[-1]
```
``` java []
import java.util.*;

class Solution {
    public int countPaths(int n, int[][] roads) {
        int mod = 1_000_000_007;
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();

        for (int[] r : roads) {
            adj[r[0]].add(new int[]{r[1], r[2]});
            adj[r[1]].add(new int[]{r[0], r[2]});
        }

        long[] shortesttime = new long[n];
        int[] cnt = new int[n];
        Arrays.fill(shortesttime, Long.MAX_VALUE);

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

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

            if (time > shortesttime[node]) continue;

            for (int[] edge : adj[node]) {
                int nbr = edge[0], rtime = edge[1];

                if (time + rtime < shortesttime[nbr]) {
                    shortesttime[nbr] = time + rtime;
                    cnt[nbr] = cnt[node];
                    pq.offer(new long[]{shortesttime[nbr], nbr});
                } else if (time + rtime == shortesttime[nbr]) {
                    cnt[nbr] = (cnt[nbr] + cnt[node]) % mod;
                }
            }
        }

        return cnt[n - 1];
    }
}
```
```js []
var countPaths = function(n, roads) {
    const mod = 1e9 + 7;
    const adj = Array.from({ length: n }, () => []);
    
    for (const [u, v, t] of roads) {
        adj[u].push([v, t]);
        adj[v].push([u, t]);
    }

    const shortestTime = Array(n).fill(Infinity);
    const cnt = Array(n).fill(0);
    const minHeap = [[0, 0]]; // [time, node]

    shortestTime[0] = 0;
    cnt[0] = 1;

    while (minHeap.length) {
        minHeap.sort((a, b) => a[0] - b[0]); // Ensure it's a min-heap
        const [time, node] = minHeap.shift();

        if (time > shortestTime[node]) continue;

        for (const [nbr, rtime] of adj[node]) {
            if (time + rtime < shortestTime[nbr]) {
                shortestTime[nbr] = time + rtime;
                cnt[nbr] = cnt[node];
                minHeap.push([shortestTime[nbr], nbr]);
            } else if (time + rtime === shortestTime[nbr]) {
                cnt[nbr] = (cnt[nbr] + cnt[node]) % mod;
            }
        }
    }

    return cnt[n - 1];
};

```
```C# []
using System;
using System.Collections.Generic;

public class Solution {
    public int CountPaths(int n, int[][] roads) {
        int mod = 1_000_000_007;
        var adj = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) adj[i] = new List<(int, int)>();

        foreach (var road in roads) {
            adj[road[0]].Add((road[1], road[2]));
            adj[road[1]].Add((road[0], road[2]));
        }

        long[] shortestTime = new long[n];
        Array.Fill(shortestTime, long.MaxValue);
        int[] cnt = new int[n];
        var pq = new SortedSet<(long, int)> { (0, 0) };

        shortestTime[0] = 0;
        cnt[0] = 1;

        while (pq.Count > 0) {
            var (time, node) = pq.Min;
            pq.Remove(pq.Min);

            if (time > shortestTime[node]) continue;

            foreach (var (nbr, rtime) in adj[node]) {
                if (time + rtime < shortestTime[nbr]) {
                    pq.Remove((shortestTime[nbr], nbr));
                    shortestTime[nbr] = time + rtime;
                    cnt[nbr] = cnt[node];
                    pq.Add((shortestTime[nbr], nbr));
                }
                else if (time + rtime == shortestTime[nbr]) {
                    cnt[nbr] = (cnt[nbr] + cnt[node]) % mod;
                }
            }
        }

        return cnt[n - 1];
    }
}
```
```php []
function countPaths($n, $roads) {
    $mod = 1e9 + 7;
    $adj = array_fill(0, $n, []);
    foreach ($roads as $road) {
        $adj[$road[0]][] = [$road[1], $road[2]];
        $adj[$road[1]][] = [$road[0], $road[2]];
    }

    $shortestTime = array_fill(0, $n, PHP_INT_MAX);
    $cnt = array_fill(0, $n, 0);
    $pq = new SplPriorityQueue();
    $pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

    $shortestTime[0] = 0;
    $cnt[0] = 1;
    $pq->insert([0, 0], 0);

    while (!$pq->isEmpty()) {
        $current = $pq->extract();
        [$time, $node] = $current['data'];

        if ($time > $shortestTime[$node]) continue;

        foreach ($adj[$node] as [$nbr, $rtime]) {
            if ($time + $rtime < $shortestTime[$nbr]) {
                $shortestTime[$nbr] = $time + $rtime;
                $cnt[$nbr] = $cnt[$node];
                $pq->insert([$shortestTime[$nbr], $nbr], -$shortestTime[$nbr]);
            } elseif ($time + $rtime === $shortestTime[$nbr]) {
                $cnt[$nbr] = ($cnt[$nbr] + $cnt[$node]) % $mod;
            }
        }
    }

    return $cnt[$n - 1];
}
```
```ruby []
def count_paths(n, roads)
    mod = 1_000_000_007
    adj = Array.new(n) { [] }

    roads.each do |u, v, t|
        adj[u] << [v, t]
        adj[v] << [u, t]
    end

    shortest_time = Array.new(n, Float::INFINITY)
    cnt = Array.new(n, 0)
    pq = [[0, 0]] # [time, node]

    shortest_time[0] = 0
    cnt[0] = 1

    until pq.empty?
        time, node = pq.shift
        next if time > shortest_time[node]

        adj[node].each do |nbr, rtime|
            if time + rtime < shortest_time[nbr]
                shortest_time[nbr] = time + rtime
                cnt[nbr] = cnt[node]
                pq << [shortest_time[nbr], nbr]
            elsif time + rtime == shortest_time[nbr]
                cnt[nbr] = (cnt[nbr] + cnt[node]) % mod
            end
        end
        pq.sort_by!(&:first)
    end

    cnt[-1]
end
```
```kotlin []
import java.util.PriorityQueue

fun countPaths(n: Int, roads: Array<IntArray>): Int {
    val mod = 1_000_000_007
    val adj = Array(n) { mutableListOf<Pair<Int, Int>>() }

    for (road in roads) {
        adj[road[0]].add(Pair(road[1], road[2]))
        adj[road[1]].add(Pair(road[0], road[2]))
    }

    val shortestTime = LongArray(n) { Long.MAX_VALUE }
    val cnt = IntArray(n) { 0 }
    val pq = PriorityQueue(compareBy<Pair<Long, Int>> { it.first })

    shortestTime[0] = 0
    cnt[0] = 1
    pq.add(Pair(0L, 0))

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

        if (time > shortestTime[node]) continue

        for ((nbr, rtime) in adj[node]) {
            if (time + rtime < shortestTime[nbr]) {
                shortestTime[nbr] = time + rtime
                cnt[nbr] = cnt[node]
                pq.add(Pair(shortestTime[nbr], nbr))
            } else if (time + rtime == shortestTime[nbr]) {
                cnt[nbr] = (cnt[nbr] + cnt[node]) % mod
            }
        }
    }

    return cnt[n - 1]
}
```
```swift []
import Foundation

func countPaths(_ n: Int, _ roads: [[Int]]) -> Int {
    let mod = 1_000_000_007
    var adj = Array(repeating: [(Int, Int)](), count: n)
    for road in roads {
        adj[road[0]].append((road[1], road[2]))
        adj[road[1]].append((road[0], road[2]))
    }

    var shortestTime = Array(repeating: Int.max, count: n)
    var cnt = Array(repeating: 0, count: n)
    var pq = [(0, 0)]
    shortestTime[0] = 0
    cnt[0] = 1

    while !pq.isEmpty {
        let (time, node) = pq.removeFirst()

        if time > shortestTime[node] { continue }

        for (nbr, rtime) in adj[node] {
            if time + rtime < shortestTime[nbr] {
                shortestTime[nbr] = time + rtime
                cnt[nbr] = cnt[node]
                pq.append((shortestTime[nbr], nbr))
            } else if time + rtime == shortestTime[nbr] {
                cnt[nbr] = (cnt[nbr] + cnt[node]) % mod
            }
        }
    }

    return cnt[n - 1]
}
```
```rust []
use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn count_paths(n: i32, roads: Vec<Vec<i32>>) -> i32 {
    let mod_val = 1_000_000_007;
    let n = n as usize;
    let mut adj = vec![vec![]; n];

    for road in roads.iter() {
        let u = road[0] as usize;
        let v = road[1] as usize;
        let t = road[2] as i64;

        adj[u].push((v, t));
        adj[v].push((u, t));
    }

    let mut shortest_time = vec![i64::MAX; n];
    let mut cnt = vec![0; n];
    let mut pq = BinaryHeap::new();

    shortest_time[0] = 0;
    cnt[0] = 1;
    pq.push(Reverse((0, 0))); // (time, node)

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

        for &(nbr, rtime) in &adj[node] {
            let new_time = time + rtime;

            if new_time < shortest_time[nbr] {
                shortest_time[nbr] = new_time;
                cnt[nbr] = cnt[node];
                pq.push(Reverse((new_time, nbr)));
            } else if new_time == shortest_time[nbr] {
                cnt[nbr] = (cnt[nbr] + cnt[node]) % mod_val;
            }
        }
    }

    cnt[n - 1] as i32
}
```
```GO []
package main

import (
    "container/heap"
    "fmt"
    "math"
)

const MOD = 1_000_000_007

type Pair struct {
    time, node int
}

type MinHeap []Pair

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].time < h[j].time }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(Pair))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func countPaths(n int, roads [][]int) int {
    adj := make([][]Pair, n)
    for _, road := range roads {
        u, v, t := road[0], road[1], road[2]
        adj[u] = append(adj[u], Pair{t, v})
        adj[v] = append(adj[v], Pair{t, u})
    }

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

    pq := &MinHeap{{0, 0}}
    heap.Init(pq)

    for pq.Len() > 0 {
        top := heap.Pop(pq).(Pair)
        time, node := top.time, top.node

        if time > shortestTime[node] {
            continue
        }

        for _, neighbor := range adj[node] {
            nbr, rtime := neighbor.node, neighbor.time
            newTime := time + rtime

            if newTime < shortestTime[nbr] {
                shortestTime[nbr] = newTime
                cnt[nbr] = cnt[node]
                heap.Push(pq, Pair{newTime, nbr})
            } else if newTime == shortestTime[nbr] {
                cnt[nbr] = (cnt[nbr] + cnt[node]) % MOD
            }
        }
    }

    return cnt[n-1]
}

func main() {
    roads := [][]int{{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 1}}
    fmt.Println(countPaths(4, roads)) // Output: 2
}
```
![image.png](https://assets.leetcode.com/users/images/3eab92e0-d5d4-4f62-a9f2-f3af01c84995_1742696923.819687.png)


['Swift', 'Python', 'C++', 'Java', 'Go', 'Rust', 'Ruby', 'Kotlin', 'JavaScript', 'C#']