Dijkstra once with DP||beats 100%
IntuitionShortest Path problem.
Apply Dijkstra's Agorithm once with considering DP, it can solve the problem.ApproachIt's my Dijkstra's collection https://leetc
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Shortest Path problem.
Apply Dijkstra's Agorithm once with considering DP, it can solve the problem.
# Approach
<!-- Describe your approach to solving the problem. -->
It's my Dijkstra's collection [https://leetcode.com/problem-list/azox743c/](https://leetcode.com/problem-list/azox743c/)
 Use Dijkstra's algorithm.
[LC 1631. [Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/solutions/4049711/c-dijkstra-s-algorithm-vs-dfs-binary-search-vs-union-find-pseudo-metric-91-ms-beats-98-93/). Please turn on English subtitles if necessary]
[https://youtu.be/IkpRzCICL_g?si=B4CSph1_mygXYB2w](https://youtu.be/IkpRzCICL_g?si=B4CSph1_mygXYB2w)
1. Let `vector<int2> adj[200]` be a global variable; due to my experience of allocation for 2D array is time consumming, let's perform only once.
2. define `dijkstra(int start, int n, unsigned long long* dist)` to find the distances for the shortest paths to all nodes & stored in `dist[]`. Using `unsigned long long way[n]` as DP state matrix.
3. In the implementation for Dijkstra's algo, a min heap ` pq` is used for which it contains the info pair `(distance, index)`. the whole process is proceeded by a BFS over `pq`. The DP part is using the argument `paths thru i & not thru i` when `newD==dist[j]`!!!!!
3. In `int countPaths(int n, vector<vector<int>>& roads)`, firstly clear `adj[i]` for every i
4. Build the adjacent list with the info pairs `(time, v) & (time, w)` for weighted edge (v, w) with weight `time`
5. Declare the array `dist[200]` & filled with `ULLONG_MAX`
6. Perform `dijkstra(0, n, dist)` once and return the answer.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O((n+|roads|)\log n)$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(n)$
# Code||C++ 0ms beats 100%
```cpp []
const int mod=1e9+7;
using int2=pair<unsigned long long, int>;
vector<int2> adj[200];
class Solution {
public:
    unsigned long long dijkstra(int start, int n, unsigned long long* dist){
        unsigned long long way[n];
        memset(way, 0, sizeof(way));
        priority_queue<int2, vector<int2>, greater<int2>> pq;
        pq.emplace(0, start);
        dist[start]=0;
        way[start]=1;
        while(!pq.empty()){
            auto [d0, i]=pq.top();
            pq.pop();
            for(auto [d2, j]:adj[i]){
                unsigned long long newD=d0+d2;
                if (newD<dist[j]){// path thru i, j
                    dist[j]=newD;
                    way[j]=way[i];
                    pq.emplace(newD, j);
                }
                else if( newD==dist[j]){
                    way[j]+=way[i]; // paths thru i & not thru i
                    way[j]%=mod;
                }
            }
        }
        return way[n-1];
    }
    int countPaths(int n, vector<vector<int>>& roads) {
        for(int i=0; i<n; i++)
            adj[i].clear();
            
        for (auto& e: roads){
            int u=e[0], v=e[1];
            unsigned long long time=e[2];
            adj[u].emplace_back(time, v);
            adj[v].emplace_back(time, u);
        }
        unsigned long long dist[200];
        fill(dist, dist+n, ULLONG_MAX);
        return dijkstra(0, n, dist);
    }
};
```
['Dynamic Programming', 'Shortest Path', 'C++']