C++ || Dijkstra algorithm
Time Complexity=O(V+E)\nSpace Complexity=O(V+E)\nV=number of node\nE=number of edges\n\n\n  \n    #define ll long long\n    class Solution {\n    public:\n    i
**Time Complexity=O(V+E)\nSpace Complexity=O(V+E)**\nV=number of node\nE=number of edges\n\n\n  \n    #define ll long long\n    class Solution {\n    public:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<pair<ll,ll>> adj[n];\n        for(auto it:roads){\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<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;\n        vector<ll> ways(n,0),dist(n,LONG_MAX);\n        pq.push({0,0});\n        dist[0]=0;\n        ways[0]=1;\n        int mod=1e9+7;\n        \n        while(!pq.empty()){\n            ll dis=pq.top().first;\n            ll node=pq.top().second;\n            pq.pop();\n            \n            for(auto it:adj[node]){\n                ll adjNode=it.first;\n                ll edgeW=it.second;\n                \n                if(edgeW+dis< dist[adjNode]){\n                    dist[adjNode]=edgeW+dis;\n                    pq.push({edgeW+dis,adjNode});\n                    ways[adjNode]=ways[node];\n                }\n                else if(edgeW+dis==dist[adjNode]){\n                    ways[adjNode]=(ways[adjNode]+ways[node])%mod;\n                }\n                \n            }\n        }\n        return ways[n-1]%mod;\n    }\n    };\n\t\n\t/**Please Don\'t forget to Upvote the post**/\n\n\n
['Graph', 'C']