Number of Ways to Arrive at Destination — Dijkstra + Count

import heapq

def countPaths(n, roads):
    MOD = 10**9+7
    adj = [[] for _ in range(n)]
    for u, v, w in roads:
        adj[u].append((v, w))
        adj[v].append((u, w))

    dist = [float('inf')]*n
    ways = [0]*n
    dist[0] = 0
    ways[0] = 1
    heap = [(0, 0)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in adj[u]:
            nd = d+w
            if nd < dist[v]:
                dist[v] = nd
                ways[v] = ways[u]
                heapq.heappush(heap, (nd, v))
            elif nd == dist[v]:
                ways[v] = (ways[v]+ways[u]) % MOD
    return ways[n-1]

function countPaths(n, roads) {
    const MOD=1e9+7, adj=Array.from({length:n},()=>[]);
    for(const[u,v,w]of roads){adj[u].push([v,w]);adj[v].push([u,w]);}
    const dist=new Array(n).fill(Infinity), ways=new Array(n).fill(0);
    dist[0]=0; ways[0]=1;
    const heap=[[0,0]];
    const pop=()=>{let mi=0;for(let i=1;i<heap.length;i++)if(heap[i][0]<heap[mi][0])mi=i;return heap.splice(mi,1)[0];};
    while(heap.length){const[d,u]=pop();if(d>dist[u])continue;
        for(const[v,w]of adj[u]){const nd=d+w;if(nd<dist[v]){dist[v]=nd;ways[v]=ways[u];heap.push([nd,v]);}else if(nd===dist[v])ways[v]=(ways[v]+ways[u])%MOD;}}
    return ways[n-1];
}

import java.util.*;
public int countPaths(int n, int[][] roads) {
    int MOD=1_000_000_007; List<long[]>[]adj=new List[n]; for(int i=0;i<n;i++)adj[i]=new ArrayList<>();
    for(int[]r:roads){adj[r[0]].add(new long[]{r[1],r[2]});adj[r[1]].add(new long[]{r[0],r[2]});}
    long[]dist=new long[n],ways=new long[n]; Arrays.fill(dist,Long.MAX_VALUE/2); dist[0]=0; ways[0]=1;
    PriorityQueue<long[]>pq=new PriorityQueue<>(Comparator.comparingLong(a->a[0])); pq.offer(new long[]{0,0});
    while(!pq.isEmpty()){long[]top=pq.poll();long d=top[0];int u=(int)top[1];if(d>dist[u])continue;
        for(long[]nb:adj[u]){long nd=d+nb[1];int v=(int)nb[0];if(nd<dist[v]){dist[v]=nd;ways[v]=ways[u];pq.offer(new long[]{nd,v});}else if(nd==dist[v])ways[v]=(ways[v]+ways[u])%MOD;}}
    return(int)ways[n-1];
}

#include <vector>
#include <queue>
using namespace std;
int countPaths(int n,vector<vector<int>>&roads){
    const int MOD=1e9+7; vector<vector<pair<long long,int>>>adj(n);
    for(auto&r:roads){adj[r[0]].push_back({r[2],r[1]});adj[r[1]].push_back({r[2],r[0]});}
    vector<long long>dist(n,LLONG_MAX/2); vector<long long>ways(n,0); dist[0]=0;ways[0]=1;
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>>pq; pq.push({0,0});
    while(!pq.empty()){auto[d,u]=pq.top();pq.pop();if(d>dist[u])continue;
        for(auto[w,v]:adj[u]){long long nd=d+w;if(nd<dist[v]){dist[v]=nd;ways[v]=ways[u];pq.push({nd,v});}else if(nd==dist[v])ways[v]=(ways[v]+ways[u])%MOD;}}
    return ways[n-1];
}

/* C: Dijkstra with dist[] and ways[] arrays, struct heap */