C++ | Dijkstra | Number of ways to arrive at destination
\nclass Solution {\npublic:\n    const int MOD = 1e9+7;\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<long long> dist(n,1e18), path(n
```\nclass Solution {\npublic:\n    const int MOD = 1e9+7;\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<long long> dist(n,1e18), path(n,0);\n        vector<vector<pair<int,int>>> g(n);\n        for(int i=0; i<roads.size(); i++){\n            g[roads[i][0]].push_back({roads[i][1],roads[i][2]});\n            g[roads[i][1]].push_back({roads[i][0],roads[i][2]});\n\n        }\n        priority_queue<pair<long long,int>> pq;\n        pq.push({0,0});\n        dist[0]=0;\n        path[0]=1;\n        while(!pq.empty()){\n            auto cur = pq.top();\n            pq.pop();\n            int node = cur.second;\n            long long d = -cur.first;\n            for(auto x: g[node]){\n                if(dist[x.first]>d + x.second){\n                    dist[x.first]=d+x.second;\n                    pq.push({-dist[x.first],x.first});\n                    path[x.first]=path[node];\n                }else if(dist[x.first]==d+x.second){\n                    path[x.first]= (path[x.first] + path[node]);\n                    if(path[x.first]>=MOD) path[x.first]-=MOD;\n                }\n            }\n        }\n        \n        return path[n-1];\n    }\n};\n```
['Math', 'C']