Number of Restricted Paths From First to Last Node solution and explanation

import heapq

MOD = 10**9 + 7

def countRestrictedPaths(n, edges):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # Step 1: Find shortest paths from node n to every other node
    dist = [float('inf')] * (n + 1)
    dist[n] = 0
    min_heap = [(0, n)]
    
    while min_heap:
        d, current = heapq.heappop(min_heap)
        if d > dist[current]:
            continue
        for neighbor, weight in graph[current]:
            if dist[current] + weight < dist[neighbor]:
                dist[neighbor] = dist[current] + weight
                heapq.heappush(min_heap, (dist[neighbor], neighbor))
    
    # Step 2: Count restricted paths using DFS + Memoization
    memo = {}
    def dfs(node):
        if node == n:
            return 1
        if node in memo:
            return memo[node]
        
        total_paths = 0
        for neighbor, _ in graph[node]:
            if dist[neighbor] < dist[node]:
                total_paths += dfs(neighbor)
                total_paths %= MOD
        
        memo[node] = total_paths
        return total_paths
    
    return dfs(1)

const MOD = 10**9 + 7;

function countRestrictedPaths(n, edges) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v, w] of edges) {
        graph[u].push([v, w]);
        graph[v].push([u, w]);
    }
    
    const dist = Array(n + 1).fill(Infinity);
    dist[n] = 0;
    const minHeap = [[0, n]];
    
    while (minHeap.length) {
        const [d, node] = minHeap.pop();
        if (d > dist[node]) continue;
        
        for (const [neighbor, weight] of graph[node]) {
            if (dist[node] + weight < dist[neighbor]) {
                dist[neighbor] = dist[node] + weight;
                minHeap.push([dist[neighbor], neighbor]);
                minHeap.sort(([a], [b]) => b - a); // simulate priority queue
            }
        }
    }

    const memo = {};

    function dfs(node) {
        if (node === n) return 1;
        if (memo[node] != null) return memo[node];

        let totalPaths = 0;
        for (const [neighbor] of graph[node]) {
            if (dist[neighbor] < dist[node]) {
                totalPaths = (totalPaths + dfs(neighbor)) % MOD;
            }
        }

        memo[node] = totalPaths;
        return totalPaths;
    }

    return dfs(1);
}

import java.util.*;

public class Solution {
    private static final int MOD = 1_000_000_007;
    
    public int countRestrictedPaths(int n, int[][] edges) {
        List<int[]>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(new int[]{edge[1], edge[2]});
            graph[edge[1]].add(new int[]{edge[0], edge[2]});
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[n] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, n});

        while (!pq.isEmpty()) {
            int[] node = pq.poll();
            int d = node[0], u = node[1];
            if (d > dist[u]) continue;

            for (int[] neighbor : graph[u]) {
                int v = neighbor[0], w = neighbor[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }

        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) {
            order[i] = i + 1;
        }
        Arrays.sort(order, Comparator.comparingInt(a -> dist[a]));

        int[] dp = new int[n + 1];
        dp[n] = 1;

        for (int u : order) {
            for (int[] neighbor : graph[u]) {
                int v = neighbor[0];
                if (dist[v] < dist[u]) {
                    dp[u] = (dp[u] + dp[v]) % MOD;
                }
            }
        }

        return dp[1];
    }
}

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;

int countRestrictedPaths(int n, vector<vector<int>>& edges) {
    vector<vector<pair<int, int>>> graph(n + 1);
    for (auto& edge : edges) {
        graph[edge[0]].emplace_back(edge[1], edge[2]);
        graph[edge[1]].emplace_back(edge[0], edge[2]);
    }
    
    vector<long long> dist(n + 1, LLONG_MAX);
    dist[n] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    pq.emplace(0, n);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto& [v, w] : graph[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }

    vector<int> dp(n + 1, -1);
    vector<int> sortedNodes;
    for (int i = 1; i <= n; ++i) {
        sortedNodes.push_back(i);
    }
    sort(sortedNodes.begin(), sortedNodes.end(), [&](int a, int b) {
        return dist[a] < dist[b];
    });

    function<int(int)> dfs = [&](int node) {
        if (node == n) return 1;
        if (dp[node] != -1) return dp[node];

        int totalPaths = 0;
        for (auto& [v, w] : graph[node]) {
            if (dist[v] < dist[node]) {
                totalPaths = (totalPaths + dfs(v)) % MOD;
            }
        }
        return dp[node] = totalPaths;
    };

    return dfs(1);
}

const inf = math.MaxInt32
const mod = 1e9 + 7

type pair struct {
	first  int
	second int
}

var _ heap.Interface = (*pairs)(nil)

type pairs []pair

func (a pairs) Len() int { return len(a) }
func (a pairs) Less(i int, j int) bool {
	return a[i].first < a[j].first || a[i].first == a[j].first && a[i].second < a[j].second
}
func (a pairs) Swap(i int, j int) { a[i], a[j] = a[j], a[i] }
func (a *pairs) Push(x any)       { *a = append(*a, x.(pair)) }
func (a *pairs) Pop() any         { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }

func countRestrictedPaths(n int, edges [][]int) int {
	g := make([]pairs, n+1)
	for _, e := range edges {
		u, v, w := e[0], e[1], e[2]
		g[u] = append(g[u], pair{v, w})
		g[v] = append(g[v], pair{u, w})
	}
	dist := make([]int, n+1)
	f := make([]int, n+1)
	for i := range dist {
		dist[i] = inf
		f[i] = -1
	}
	dist[n] = 0
	h := make(pairs, 0)
	heap.Push(&h, pair{0, n})
	for len(h) > 0 {
		u := heap.Pop(&h).(pair).second
		for _, ne := range g[u] {
			v, w := ne.first, ne.second
			if dist[v] > dist[u]+w {
				dist[v] = dist[u] + w
				heap.Push(&h, pair{dist[v], v})
			}
		}
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if f[i] != -1 {
			return f[i]
		}
		if i == n {
			return 1
		}
		ans := 0
		for _, ne := range g[i] {
			j := ne.first
			if dist[i] > dist[j] {
				ans = (ans + dfs(j)) % mod
			}
		}
		f[i] = ans
		return ans
	}
	return dfs(1)
}