C++ Dijkstra Solution O(V^2 LogV)
Runtime: 96 ms, faster than 46.70% of C++ online submissions for Number of Ways to Arrive at Destination.\nMemory Usage: 40.5 MB, less than 7.91% of C++ online 
Runtime: 96 ms, faster than 46.70% of C++ online submissions for Number of Ways to Arrive at Destination.\nMemory Usage: 40.5 MB, less than 7.91% of C++ online submissions for Number of Ways to Arrive at Destination.\n\nNote: Solution taken from other post.\n\n```\nWe can find the shortest distance from any vertex to another using Dijkstra Algo in a weighted graph. \nHere we have to find the number of ways we can go from source to destination and so we keep an array\nto store the ways count for all nodes as we progress in Dijkstra Algo and use it for the neighbor nodes\nwhich is actually a DP approach. \n\nNow, each time we relax the cost of neighbor node we find a better distance for neighbor node and so \nthe number of way to go to neighbor node = number way to come to the current node and so we update \nthe ways[neighbor] = ways[node]. Also when we see that neighbor node cost and current node \ncost + edge cost is same then this is another way to go to the neighbor node with min cost and so we \nupdate neighbor node ways count as ways[neighbor] += ways[node]. Also when pop a node with cost \ngreater than the current cost of the node then we will ignore the furthur operations cause the cost \nis higher and we need to find min cost paths.\n```\n\n```\nclass Solution {\npublic:\n        \n    int countPaths(int n, vector<vector<int>>& roads) {\n        \n        // Adjacency list of the undirected graph\n        vector<vector<vector<int>>>adjL(n);\n        \n        // distance vector of nodes\n        vector<long>dist(n,LONG_MAX);\n        \n        // populate Adjacency List {node, cost} pair\n        for(int i=0;i<roads.size();i++)\n        {\n            adjL[roads[i][0]].push_back({roads[i][1],roads[i][2]});\n            adjL[roads[i][1]].push_back({roads[i][0],roads[i][2]});\n        }\n        \n        int MOD = 1000000007;\n        \n        // track the number of ways to reach node with min cost\n        vector<long>ways(n,0);\n        \n        // source node has way 1 \n        ways[0] = 1;\n        \n        // push source node with distance 0, PQ stores {cost, node} pair\n        priority_queue<pair<long,int>,vector<pair<long,int>>,greater<>>pQ;\n        pQ.push({0,0});\n        dist[0] = 0;\n        \n        long cost;\n        int node;        \n        while(!pQ.empty())\n        {\n            cost = pQ.top().first;\n            node = pQ.top().second;\n            pQ.pop();\n            \n            // if cost is higher than current node distance then we ignroe furthur operations\n            if(dist[node]<cost)continue;\n            \n            // loop through neighbors and relax the neighbor nodes\n            for(auto &adj: adjL[node])\n            {                \n                // relax neighbor nodes and push in to PQ\n                // neighbor node ways will be updated with current node ways as\n                // we find a better cost for neighbor node\n                if(dist[node]+adj[1] < dist[adj[0]])\n                {\n                    dist[adj[0]] = dist[node]+adj[1];\n                    ways[adj[0]] = ways[node];\n                    pQ.push({dist[adj[0]],adj[0]});\n                }\n                \n                // if current node distance + edge cost = neighbor node cost then\n                // this is another way to reach the neighbor node with min cost\n                // so we update neighbor node ways as ways[neighbor] += ways[node]\n                else if(dist[node]+adj[1] == dist[adj[0]])\n                {\n                    ways[adj[0]] = (ways[adj[0]] + ways[node])%MOD;\n                }\n            }\n        }\n\n        // return the number of ways to reach destination node\n        return ways[n-1];\n    }\n};\n```
['Dynamic Programming', 'Graph', 'C']