1976: Number-of-Ways-to-Arrive-at-Destination
Medium

table of contents

Simply put, this is just a Dijkstra’s problem, where you have to keep track of the count of paths travelling into each node. You can do this with simple dynamic programming, as the count of paths travelling into a new node depends on the previous traversals.

code

do note, that I used weight instead of time throughout this algorithm…

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int, int>>> adjacencyMatrix (n);
        for (vector<int>& road : roads) {
            int start = road[0], end = road[1], weight = road[2];
            adjacencyMatrix[start].push_back({end, weight});
            adjacencyMatrix[end].push_back({start, weight});
        }

        // tracks the number of paths going into each node
        vector<int> count (n, 0);
        // tracks the minimum_weights
        vector<long long> weights (n, LLONG_MAX);
        weights[0] = 0;
        count[0] = 1;

        // minHeap needed to greedily track the next edge to traverse
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> minHeap; 
        minHeap.push({0, 0}); 

        while (!minHeap.empty()) {
            pair<long long, int> edge = minHeap.top();
            int nontarget = edge.second;
            long long nontargetWeight = edge.first;
            minHeap.pop();

            // ignore if too heavy
            if (nontargetWeight > weights[nontarget]) continue;

            for (auto& [target, targetWeight] : adjacencyMatrix[nontarget]) {
                if (nontargetWeight + targetWeight < weights[target]) {
                    weights[target] = nontargetWeight + targetWeight;
                    count[target] = count[nontarget];
                    minHeap.push({weights[target], target});
                } else if (nontargetWeight + targetWeight == weights[target]) {
                    count[target] = (count[target] + count[nontarget]) % (int)(1e9+7);
                }
            }
        }

        return count.back();
    }
};

complexity

learnings