C++ | Using Priority Queue and Set | 2 Approaches highly commented
Using Priority Queue\ncpp\nclass Solution {\npublic:\n    /*\n        Approach: We will use the dijsktra algorithm to find out the shortest distance then calcul
**Using Priority Queue**\n```cpp\nclass Solution {\npublic:\n    /*\n        Approach: We will use the dijsktra algorithm to find out the shortest distance then calculate number of ways you can arrive at your destination in the shortest time. Take distance as long long\n        1. Using a Priority Queue\n        2. Using a Set\n        3. Using a queue (not preferred)\n    */\n    #define P pair<long long,long long> \n    long long mod = 1e9 + 7;\n    int dijkstra(vector<pair<int, int>> adj[], int n) {\n        // Priority queue for relaxing nodes (distance, nodes)\n        priority_queue<P, vector<P>, greater<P>> pq;\n        \n        // Distance vector\n        vector<long long>distance(n, 1e15), path(n, 0);\n        distance[0] = 0;\n        pq.push({0, 0});\n        path[0] = 1;\n\n        while(!pq.empty()){\n            int node = pq.top().second;\n            long long dist = pq.top().first;\n            pq.pop();\n            \n            for(auto it : adj[node]){\n                int adjNode = it.first;\n                long long edgeW = it.second;\n                \n                if(dist + edgeW < distance[adjNode]){\n                    // Relax\n                    distance[adjNode] = dist + edgeW;\n                    path[adjNode] = path[node];\n                    pq.push({distance[adjNode], adjNode});\n                }else if(dist + edgeW == distance[adjNode]){\n                    // Node is already visited with the shortes path, sum of parent and the current node path\n                    path[adjNode] = (1LL*path[node] + 1LL*path[adjNode]) % mod;\n                }\n            }\n        }\n        return path[n - 1];\n    }\n    int countPaths(int n, vector<vector<int>>& roads) {\n        \n        \n         // First step for grpah question is to create the adjacency list\n        vector<pair<int, int>> adj[n];\n\n        // Graph Creation\n        for (auto &v : roads) {\n            adj[v[0]].push_back({v[1], v[2]});\n            adj[v[1]].push_back({v[0], v[2]});\n        }\n        \n        return dijkstra(adj, n);\n    }\n};\n```\n**Using Set**\n```cpp\nclass Solution {\npublic:\n    /*\n        Approach: We will use the dijsktra algorithm to find out the shortest distance then calculate number of ways you can arrive at your destination in the shortest time. Take distance as long long\n        1. Using a Priority Queue\n        2. Using a Set\n        3. Using a queue (not preferred)\n    */\n    long long mod = 1e9 + 7;\n    int dijkstra2(vector<pair<int, int>> adj[], int n) {\n     // Set for relaxing nodes (distance, nodes), in set we can delete if we found dist != INF but it will also takes up O(logn)\n        set<pair <long, long>> st;\n        \n        // Distance vector\n        vector<long long>distance(n, 1e15), path(n, 0);\n        distance[0] = 0;\n        st.insert({0, 0});\n        path[0] = 1;\n\n        while(!st.empty()){\n            auto itr = *(st.begin());\n            int node = itr.second;\n            long long dist = itr.first;\n            st.erase(itr);\n            \n            for(auto it : adj[node]){\n                int adjNode = it.first;\n                long long edgeW = it.second;\n                \n                if(dist + edgeW < distance[adjNode]){\n                    if(distance[adjNode] != 1e9)st.erase({distance[adjNode], adjNode});\n                    \n                    // Relax\n                    distance[adjNode] = dist + edgeW;\n                    \n                    // Path Update\n                    path[adjNode] = path[node];\n                    \n                    // Inserting Back \n                    st.insert({distance[adjNode], adjNode});\n                }else if(dist + edgeW == distance[adjNode]){\n                    // Node is already visited with the shortes path, sum of parent and the current node path\n                    path[adjNode] = (1LL*path[node] + 1LL*path[adjNode]) % mod;\n                }\n            }\n        }\n        return path[n - 1];\n    }\n    \n    int countPaths(int n, vector<vector<int>>& roads) {\n         // First step for grpah question is to create the adjacency list\n        vector<pair<int, int>> adj[n];\n\n        // Graph Creation\n        for (auto &v : roads) {\n            adj[v[0]].push_back({v[1], v[2]});\n            adj[v[1]].push_back({v[0], v[2]});\n        }\n        \n        return dijkstra2(adj, n);\n    }\n};\n```
['Graph', 'C', 'Heap (Priority Queue)', 'Ordered Set', 'C++']