Dijkstra N log(n) | Greedy Logic
IntuitionWe can observe that this is a shortest path problem. So Dijkstra or similar algorithm comes quickly to intuition. We will be using Dijkstra.
We can als
# Intuition
We can observe that this is a shortest path problem. So Dijkstra or similar algorithm comes quickly to intuition. We will be using Dijkstra.
We can also notice one more thing , that all the ways which go from 0 to n-1 have same weighted distance which , overall is the shortest path from 0 to n-1.


<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
We can follow these sequential steps
1) Find the weight of shortest path between 0 to n-1;
2) A standard way of counting number of ways is to use this property, 
 ( if we can reach a node 'A' using x ways and node 'B' using y ways , and we can reach node 'A' from 'B' or vice versa, then totl ways will be ways[A]+ways[B]( if both have same shortest distance in path), if node A gives shorter distance , then ways[B] = ways[A]).
3) By using this property , we can simply calculate the ways in Dijkstra loop using Priority Queue
4) For simplicity and overflow avoidance, I have used long long , and converted it to integer when returning.
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
 O(m log n) :
 Where: m is the number of edges in the graph and n is the number of nodes.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n+m)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
#define ll long long
class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        ll mod = 1e9+7;
        vector<vector<pair<ll,ll>>>adj(n);
        for(ll i = 0;i<roads.size();i++){
            ll u = roads[i][0];
            ll v = roads[i][1];
            ll wt = roads[i][2];
            adj[u].push_back({wt,v});
            adj[v].push_back({wt,u}); 
        }
        vector<ll>dist(n,LLONG_MAX);
        dist[0]=0;
        vector<ll>ways(n,0);
        ways[0]=1;
        priority_queue<pair<ll,ll>>pq;
        pq.push({0,0});
        while(!pq.empty()){
            ll node = pq.top().second;
            ll wt = -(pq.top().first);
            pq.pop();
            for(auto it:adj[node]){
                ll newNode = it.second;
                ll newWt = it.first;
                if(wt+newWt <dist[newNode]){
                    dist[newNode] = newWt+wt;
                    pq.push({-(newWt+wt),newNode});
                    ways[newNode] = ways[node];
                }
                else if(wt+newWt == dist[newNode]){
                    ways[newNode] = (ways[newNode]+ways[node])%mod;
                }
            }
        }
        return (int)ways[n-1]%mod;  
    }
};
```
```java []
import java.util.*;

class Solution {
    public int countPaths(int n, int[][] roads) {
        final long MOD = 1000000007L;
        
        List<List<long[]>> adj = new ArrayList<>();
        for (long i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        
        for (int i = 0; i < roads.length; i++) {
            int u = roads[i][0];
            int v = roads[i][1];
            long wt = roads[i][2];
            adj.get(u).add(new long[]{wt, v});
            adj.get(v).add(new long[]{wt, u});
        }
        
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;
        
        long[] ways = new long[n];
        ways[0] = 1;
        
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, 0});
        
        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long node = current[1];
            long wt = current[0];
            
            for (long[] edge : adj.get((int) node)) {
                long newNode = edge[1];
                long newWt = edge[0];
                
                if (wt + newWt < dist[(int) newNode]) {
                    dist[(int) newNode] = wt + newWt;
                    pq.offer(new long[]{wt + newWt, newNode});
                    ways[(int) newNode] = ways[(int) node];
                } else if (wt + newWt == dist[(int) newNode]) {
                    ways[(int) newNode] = (ways[(int) newNode] + ways[(int) node]) % MOD;
                }
            }
        }
        
        return (int) (ways[n - 1] % MOD);
    }
}

```
```python []
import heapq

MOD = 1000000007

class Solution:
    def countPaths(self, n, roads):
        adj = [[] for _ in range(n)]
        
        # Build the graph
        for u, v, wt in roads:
            adj[u].append((wt, v))
            adj[v].append((wt, u))
        
        dist = [float('inf')] * n
        dist[0] = 0
        
        ways = [0] * n
        ways[0] = 1
        
        pq = [(0, 0)]  # (distance, node)
        
        while pq:
            wt, node = heapq.heappop(pq)
            
            for newWt, newNode in adj[node]:
                if wt + newWt < dist[newNode]:
                    dist[newNode] = wt + newWt
                    heapq.heappush(pq, (dist[newNode], newNode))
                    ways[newNode] = ways[node]
                elif wt + newWt == dist[newNode]:
                    ways[newNode] = (ways[newNode] + ways[node]) % MOD
        
        return int(ways[n - 1] % MOD)

```
 
 
['Greedy', 'Shortest Path', 'C++', 'Java', 'Python3']