[C++] Dijkstra - Clean & Concise
\ntypedef long long ll;\nconst ll mod=1e9+7;\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        int m=roads.size();\n 
```\ntypedef long long ll;\nconst ll mod=1e9+7;\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        int m=roads.size();\n        vector<vector<pair<int,int>>>v(n);\n        for(auto x: roads){\n            v[x[0]].push_back({x[1],x[2]});\n            v[x[1]].push_back({x[0],x[2]});\n        }\n        vector<ll>dis(n,LLONG_MAX);\n        vector<ll>path(n,0);\n        priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;\n        path[0]=1;\n        dis[0]=0;\n        pq.push({0,0});\n        while(!pq.empty()){\n            pair<ll,ll>p=pq.top();\n            pq.pop();\n            for(auto x: v[p.second]){\n                ll u=x.first;\n                ll w=x.second;\n                if(dis[u]>dis[p.second]+w){\n                    dis[u]=dis[p.second]+w;\n                    path[u]=path[p.second];\n                    path[u]%=mod;\n                    pq.push({dis[u],u});\n                }\n                else if(dis[u]==p.first+w){\n                    path[u]+=path[p.second];\n                    path[u]%=mod;\n                }\n            }\n        }\n        return path[n-1];\n    }\n};\n```
[]