#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

vector<int> dijkstra(int n, vector<vector<pair<int, int>>>& adj) {
    vector<int> dist(n, INT_MAX);
    dist[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0});  // {distance, node}

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int time = edge.second;

            if (dist[u] + time < dist[v]) {
                dist[v] = dist[u] + time;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int countWays(int n, vector<vector<pair<int, int>>>& adj, vector<int>& dist) {
    vector<long long> dp(n, 0);
    dp[0] = 1;
    
    vector<vector<int>> dag(n);
    for (int u = 0; u < n; ++u) {
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int time = edge.second;

            if (dist[u] + time == dist[v]) {
                dag[u].push_back(v);
            }
        }
    }

    queue<int> q;
    q.push(0);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : dag[u]) {
            dp[v] = (dp[v] + dp[u]) % MOD;
            q.push(v);
        }
    }

    return dp[n - 1];
}

int countPaths(int n, vector<vector<int>>& roads) {
    vector<vector<pair<int, int>>> adj(n);

    for (auto& road : roads) {
        int u = road[0];
        int v = road[1];
        int time = road[2];
        adj[u].push_back({v, time});
        adj[v].push_back({u, time});
    }

    vector<int> dist = dijkstra(n, adj);
    return countWays(n, adj, dist);
}

int main() {
    int n = 7;
    vector<vector<int>> roads = {
        {0, 6, 7}, {0, 1, 2}, {1, 2, 3}, {1, 3, 3}, {6, 3, 3},
        {3, 5, 1}, {6, 5, 1}, {2, 5, 1}, {0, 4, 5}, {4, 6, 2}
    };

    cout << countPaths(n, roads) << endl;  // Output: 4
    return 0;
}
.

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int countPaths(int n, vector<vector<int>>& roads) {
    vector<vector<pair<int, int>>> adj(n);
    
    // Build adjacency list
    for (auto& road : roads) {
        int u = road[0];
        int v = road[1];
        int time = road[2];
        adj[u].push_back({v, time});
        adj[v].push_back({u, time});
    }
    
    // Dijkstra's algorithm with a priority queue
    vector<int> dist(n, INT_MAX);
    vector<int> ways(n, 0);
    dist[0] = 0;
    ways[0] = 1;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0}); // {distance, node}
    
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int time = edge.second;
            
            if (dist[u] + time < dist[v]) {
                dist[v] = dist[u] + time;
                ways[v] = ways[u]; // reset ways count for v
                pq.push({dist[v], v});
            } else if (dist[u] + time == dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD; // increment ways count for v
            }
        }
    }
    
    return ways[n - 1];
}

int main() {
    int n = 7;
    vector<vector<int>> roads = {
        {0, 6, 7}, {0, 1, 2}, {1, 2, 3}, {1, 3, 3}, {6, 3, 3},
        {3, 5, 1}, {6, 5, 1}, {2, 5, 1}, {0, 4, 5}, {4, 6, 2}
    };

    cout << countPaths(n, roads) << endl;  // Output the number of ways
    return 0;
}

Which code is better in your opinion, which approach should i learn ?