Clean Dijkstra implementation || c++
\n#define ll long long\n#define pi pair<ll , ll>\nconst int mod = 1e9+7;\n\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n
```\n#define ll long long\n#define pi pair<ll , ll>\nconst int mod = 1e9+7;\n\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        \n        \n        vector<pi> adj[n];    // node-> pair< adjNode, distance>\n        for(auto &it : roads)\n        {\n            adj[it[0]].push_back({it[1],it[2]});\n            adj[it[1]].push_back({it[0],it[2]});\n        }\n        \n        priority_queue<pi, vector<pi>, greater<pi>> pq;\n        vector<ll> d(n,LONG_MAX), cnt(n,0);\n        pq.push({0,0});\n        d[0] = 0;\n        cnt[0] = 1;\n        \n        while(!pq.empty())\n        {\n            ll node = pq.top().second;\n            ll dist = pq.top().first;\n            pq.pop();\n            \n            for(auto &it : adj[node])\n            {\n                ll nextNode = it.first;\n                ll nextDist = it.second;\n                \n                if(dist + nextDist < d[nextNode])\n                {\n                    cnt[nextNode] = cnt[node]; //just inherit the no. of shortest path found till node\n                    d[nextNode] = dist + nextDist;\n                    pq.push({d[nextNode],nextNode});\n                }\n                \n                else if(dist + nextDist == d[nextNode])\n                {\n                    cnt[nextNode] = (cnt[nextNode] + cnt[node])%mod;  //(the no. of shortest path found till node + the no. of shortest path found till nextNode)\n                }\n                \n                else continue;\n            }\n        }\n        \n        return cnt[n-1]%mod;\n    }\n};\n```
['C']