Striver's Easy C++ Approach | Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves finding the number of different shortest paths from the source nod
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves finding the number of different shortest paths from the source node to the destination node in a graph with weighted edges. We can use Dijkstra\'s algorithm to find the shortest paths and keep track of the number of ways to reach each node.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCreate an adjacency list representation of the graph using the provided roads.\nUse Dijkstra\'s algorithm to find the shortest paths from the source node to all other nodes.\nWhile traversing the graph, keep track of the number of ways to reach each node by maintaining a ways vector.\nIf there is a shorter path to a node, update the shortest distance and the number of ways to reach that node.\nIf there are multiple shortest paths to a node, update the number of ways by adding the number of ways to reach the current node.\nFinally, return the number of ways to reach the destination node.\n\n# Complexity\n- Time complexity: \nO(VlogE), where \nV is the number of vertices and \n\nE is the number of edges. This is because we use Dijkstra\'s algorithm, which has a time complexity of \nO(VlogE).\n- Space complexity: \nO(V+E), where V is the number of vertices and \nE is the number of edges. We use extra space for storing the adjacency list, priority queue, distance vector, and ways vector.\n\n# Code\n```\n#define ll long long\nclass Solution {\npublic:\nint M = 1e9 + 7;\n    int countPaths(int n, vector<vector<int>>& roads) {\n        ll src = 0;\n        // create an adjancy list\n        vector<pair<ll , ll>>adj[n];\n        for(auto it : roads){\n            int u = it[0];\n            int v = it[1];\n            int wt = it[2];\n            adj[u].push_back({v ,wt});\n            adj[v].push_back({u ,wt});\n        }\n        // time is very --> so we use the  priority queue..\n        priority_queue<pair<ll ,ll> , vector<pair<ll ,ll>> , greater<pair<ll ,ll>> >pq;\n        // push the things--> {dis ,node}\n        pq.push({0 ,0});\n\n\n        // make the distance vector \n        vector<ll>dist(n ,LLONG_MAX);\n        dist[src] = 0;\n        // make the ways vector\n        vector<ll> ways(n ,0);\n        ways[src] = 1;\n\n        while(!pq.empty()){\n            ll dis = pq.top().first;\n            ll curr_node = pq.top().second;\n            pq.pop();\n\n            for(auto it : adj[curr_node]){\n               ll neighnode = it.first;\n               ll wt = it.second;\n\n               if(dis + wt < dist[neighnode]){\n                dist[neighnode] = dis + wt;\n                pq.push({dist[neighnode] , neighnode});\n                ways[neighnode] = ways[curr_node];\n               } \n\n               else if(dis + wt == dist[neighnode]){\n                ways[neighnode] = (ways[neighnode] + ways[curr_node]) %M;\n               }\n            }\n            \n        }\n        return ways[n-1 ]%M;\n\n    }\n};\n```\n\n# Please Upvote !!!
['C++']