https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/

class Solution {
public:
    void dfs(vector<vector<pair<int,int>>> &adj,int node, vector<int>& visit,int& count,int& tTime, int cTime,int finalNode) {

        visit[node]=1;

        for(int i=0;i<adj[node].size();i++) {
            pair<int,int> x = adj[node][i];
            int n = x.first;
            int etime = x.second;
            if(n==finalNode && cTime+etime==tTime) {
                count+=1;
                continue;
            }
            if(visit[n]==0) {
               dfs(adj,n,visit,count,tTime,cTime+etime,finalNode);
            }
        }

        visit[node]=0;

    }
    int countPaths(int n, vector<vector<int>>& roads) {
     vector<vector<pair<int,int>>> adj(n);
     for (auto road:roads) {
         adj[road[0]].push_back({road[1],road[2]});
        adj[road[1]].push_back({road[0],road[2]});
     }

     int mod = 1e9+7;

     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
     vector<int> time(n,1e7);
     pq.push({0,0});


     while(!pq.empty()) {
         //Pop the node
         auto temp = pq.top();
         pq.pop();
         int t(temp.first),node(temp.second);

        for(auto x:adj[node]){
            //Find the neighbour & visit it
            int xxx = x.first;
      //    return xxx;
            int ttt = x.second;

            if(ttt+t<time[xxx]) {

                time[xxx] = ttt+t;
                if(xxx==n-1) break;
                pq.push({time[xxx],xxx});
            }
        }
     }

    int minTime = time[n-1];

    vector<int> visit(n,0);

    int count=0;
    dfs(adj,0,visit,count,minTime,0,n-1);
    return count;
    }
};