Number of Ways to Arrive at Destination

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 109 + 7.

Dijkstra with Path Counting#

This problem augments standard Dijkstra with a parallel ways[] array that tracks how many shortest paths reach each node. Every node starts with ways[node] = 0 except the source (ways[0] = 1). When we relax an edge and discover a strictly shorter path to a neighbour we reset its way count to our own (ways[next] = ways[node]); when we discover an equally short alternative path we add our way count to the neighbour's (ways[next] += ways[node]). Because Dijkstra processes nodes in non-decreasing distance order, by the time a node is finalised its ways count is already complete — no separate DP pass is needed. The complexity stays the same as plain Dijkstra: O(m log n) time and O(m + n) space.

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        const int MOD = 1e9 + 7;
        vector<vector<pair<int,int>>> adjList(n);

        for(int i=0;i<roads.size();i++)
        {
            int src = roads[i][0];
            int dst = roads[i][1];
            int time = roads[i][2];

            adjList[src].push_back({dst, time});
            adjList[dst].push_back({src, time});
        }

        vector<long long> times(n,LLONG_MAX);
        vector<int> ways(n,0);
        times[0] = 0;
        ways[0] = 1;

        // time, node
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
        pq.push({0, 0});

        while(!pq.empty())
        {
            auto it = pq.top();
            long long currTime = it.first;
            int node = it.second;
            pq.pop();

            for(auto it: adjList[node])
            {
                int next = it.first;
                long long time = it.second;

                if(currTime + time < times[next])
                {
                    times[next] = currTime + time;
                    ways[next] = ways[node];
                    pq.push({times[next], next});
                }else if(currTime + time == times[next])
                    ways[next] = (ways[next] + ways[node]) % MOD;
            }
        }
        return ways[n-1];
    }
};

Time Complexity: O(m log n), m -> number of edges, n -> number of nodes

Space Complexity: O(m+n)