C++ - Dijkstra algorithm || Easy Understanding || Beats 90 percent
Code\n\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& r) {\n        int mod=1e9+7;\n        vector<vector<pair<long long,long long>>
# Code\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& r) {\n        int mod=1e9+7;\n        vector<vector<pair<long long,long long>>>adj(n);\n        for(int i=0;i<r.size();i++){\n            adj[r[i][0]].push_back({r[i][1],r[i][2]});\n            adj[r[i][1]].push_back({r[i][0],r[i][2]});\n        }\n        vector<long long>c(n,0);\n        c[0]=1;\n        priority_queue<pair<long long,long long>, vector<pair<long long,long long>>, greater<pair<long long,long long>>> pq;\n        vector<long long int>dist(n,1e15);\n        dist[0]=0;\n        pq.push({0,0});\n        while(pq.empty()==false){\n            auto x=pq.top();\n            long long dis=x.first;\n            long long node=x.second;\n            pq.pop();\n            for(auto it:adj[node]){\n                long long wt=it.second;\n                long long y=it.first; \n                if(wt+dis<dist[y]){\n                    dist[y]=(wt+dis);\n                    pq.push({dist[y],y});\n                    c[y]=c[node];\n                }\n                else if((wt+dis)==dist[y]){\n                    c[y]=(c[y]+c[node])%mod;\n                }\n                \n            }\n        }\n        return c[n-1];\n    }\n};\n```
['C++']