C++ - Dijkstra algorithm + DP (Explained)
Idea:-\nDijkstra algorithm is being used to know the most optimal way to reach the target. \nWe are using an array to store the number of optimal ways to reach 
**Idea:-**\nDijkstra algorithm is being used to know the most optimal way to reach the target. \nWe are using an array to store the number of optimal ways to reach a node.  Let us call this\n*paths[]*\n\nLet us consider an example only for DP logic:-\n\n![image](https://assets.leetcode.com/users/images/8dad9f2b-93ec-4745-81a6-5b9a202bf84e_1629564300.8240583.png)\npaths[S] = 1 As there it is the starting node so there is only 1 way to reach it\npaths[A] = 1, paths[B] = 1, paths[C] = 1\n\nSo for the above example, there are 3 ways to reach D:-\nS->A->D (cost 3)\nS->B->D (cost 2)\nS->C->D (cost 2)\nNow there are two optimal ways which have cost of 2.\nThis can be calculated by knowing two things:-\n1) The least time taken to reach D that is 2 minutes \n2) How many ways were there to reach the predecessors through which we got the least time taken that is B and C\n\nNow as there are 2 optimal ways to reach D we can move forward to nodes E and F \nwhich follows the same principle and gives us \npaths[E] = paths[F] = 2 (Naturally because they have only one predecessor)\n\nFinally node G can be reached in two ways and both ways are optimal. \nTherefore again paths[G] = paths[E] + paths[F] = 4\nand this is how we get our answer. \n\nHere\'s the code:-\n\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n       \n        /*This is the preparation part of this problem, here we are simply \n\t\tconverting given data in the form of adjacency list which is required to\n\t\trun Dijkstra\'s algorithm */\n        vector<pair<long long int, long long int>> adj[201];\n        for(int i = 0; i < roads.size(); i++)\n        {\n            int u = roads[i][0];\n            int v = roads[i][1];\n            int w = roads[i][2];\n            \n            adj[u].push_back({v, w});\n            adj[v].push_back({u, w});\n        }\n\t\t\n        priority_queue<pair<long long, long long>> pq;\n        pq.push({0, 0});\n        vector<long long> distance(201, LLONG_MAX);\n\t\t// Following is the dp array which stores the number of ways to reach a node\n        vector<long long> paths(201, 0); \n        vector<long long> visited(201, 0);\n      \n        distance[0] = 0; //because we are starting from 0\n        paths[0] = 1;\n        \n        while(!pq.empty())\n        {\n            pair<long long, long long> p = pq.top(); pq.pop();\n            long long dist = -p.first;\n            int u = p.second;\n            if(visited[u]) continue;\n            visited[u] = 1;\n          \n            for(int i = 0; i < adj[u].size(); i++)\n            {\n                int v = adj[u][i].first;\n                long long w = adj[u][i].second;\n                \n\t\t\t\t/*this means that we\'ve found a better(less time consuming) \n\t\t\t\tway to reach v, now this better way will prevail and \n\t\t\t\twe now don\'t care about past ways therefore total number \n\t\t\t\tof ways to reach v is simply equal to the total number of ways \n\t\t\t\tto reach its parent which is u */\n                if(dist + w < distance[v]) \n                {\n                    distance[v] = dist + w;\n                    pq.push({-(dist+w), v});\n                    paths[v] = paths[u];\n                }\n\t\t\t\t/*here we have a way to reach v which is taking same amount \n\t\t\t\tof time\tas the optimal path but this time parent of v \n\t\t\t\tis different therefore we ways to reach u to current ways \n\t\t\t\tof reaching v*/\n                else if(dist+w == distance[v])\n                {\n                    paths[v] = (paths[v] + paths[u])%1000000007;\n                    pq.push({-(dist+w), v});\n                }\n            }\n        }\n       \n        return (int) paths[n-1];\n    }\n};\n```
[]