EASY Striver's Approach | C++ |
Intuition\n Describe your first thoughts on how to solve this problem. \nWe are given a graph representing cities connected by roads with varying travel times. 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe are given a graph representing cities connected by roads with varying travel times. We need to find the number of shortest paths from the source city (0) to the destination city (n-1) with the minimum time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe\'ll use Dijkstra\'s algorithm to find the shortest path from the source city to all other cities.\nWe\'ll use a priority queue to prioritize nodes based on the distance from the source city.\nWe\'ll push the source city into the priority queue with a distance of 0.\nWe\'ll create an adjacency list to represent the graph.\nWe\'ll maintain a distance vector to store the minimum time to reach each city from the source city.\nWhile the priority queue is not empty, we\'ll extract the top element and explore its neighbors.\nIf the time taken to reach a neighbor city through the current city is less than the previously stored time, we\'ll update the time and push the neighbor into the priority queue with the updated time.\nIf the time taken to reach a neighbor city through the current city is equal to the previously stored time, we\'ll increment the count of ways to reach that neighbor city by the count of ways to reach the current city.\nFinally, we return the count of ways to reach the destination city.\n\n# Complexity\n- Time complexity:\nWe visit each edge at most once, so the time complexity is O(E * log(V)), where E is the number of edges and V is the number of vertices.\n- Space complexity:\nWe use extra space for the priority queue, adjacency list, and distance vector, all of which can grow up to the size of the number of vertices. So, the space complexity is O(V).\n\n# Code\n```\n#define ll long long \nclass Solution {\n\npublic:\n    int M = 1e9+7;\n    int countPaths(int n, vector<vector<int>>& roads) {\n        ll src =0;\n        // time is vary --> so we use the prioirty 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        //make the adjList :\n        vector<pair<ll,ll>> adj[n];\n        for(auto it : roads){\n            ll u = it[0];\n            ll v = it[1];\n            ll time = it[2];\n            //undirected graph\n            adj[u].push_back({v,time});\n            adj[v].push_back({u,time});\n        }\n\n        //make dist vector\n        vector<ll> dist(n,LLONG_MAX);\n        dist[src]=0;\n        vector<ll> ways(n,0);\n        ways[src]=1;\n\n        while(!pq.empty()){\n            ll dis = pq.top().first;\n            ll node = pq.top().second;\n\n            pq.pop();\n\n            for(auto it : adj[node]){\n                ll neighNode = it.first;\n                int wt = it.second;\n\n                if(dis + wt < dist[neighNode]){\n                    dist[neighNode] = dis + wt;\n                    pq.push({dis+wt , neighNode});\n                    ways[neighNode] = ways[node];\n                }\n\n                else if(dis + wt  == dist[neighNode]){\n                    ways[neighNode] = (ways[neighNode]+ways[node])%M;\n                }\n            }\n\n        }\n        return ways[n-1]%M;\n    }\n};\n```\n# PLEASE UPVOTE
['C++']