Number of Restricted Paths From First to Last Node
Problem
An undirected weighted connected graph has n nodes labeled 1..n. Let distanceToLastNode(x) be the shortest-path distance from node n to node x. A path [z0, …, zk] is restricted when every step strictly decreases that distance: distanceToLastNode(zi) > distanceToLastNode(zi+1). Return the number of restricted paths from node 1 to node n, modulo 109 + 7.
n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]3import heapq
def countRestrictedPaths(n, edges):
MOD = 10**9 + 7
g = [[] for _ in range(n + 1)] # adjacency list
for u, v, w in edges:
g[u].append((v, w)); g[v].append((u, w))
# Dijkstra from node n: dist[x] = shortest distance to n
dist = [float('inf')] * (n + 1)
dist[n] = 0
pq = [(0, n)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in g[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
# Count restricted paths with DP, nodes in increasing dist order
ways = [0] * (n + 1)
ways[n] = 1
order = sorted(range(1, n + 1), key=lambda x: dist[x])
for u in order:
for v, w in g[u]:
if dist[u] > dist[v]: # step decreases distance
ways[u] = (ways[u] + ways[v]) % MOD
return ways[1] % MODfunction countRestrictedPaths(n, edges) {
const MOD = 1000000007n;
const g = Array.from({ length: n + 1 }, () => []); // adjacency list
for (const [u, v, w] of edges) { g[u].push([v, w]); g[v].push([u, w]); }
// Dijkstra from node n: dist[x] = shortest distance to n
const dist = new Array(n + 1).fill(Infinity);
dist[n] = 0;
const pq = [[0, n]]; // simple binary-search heap
while (pq.length) {
const [d, u] = pq.shift();
if (d > dist[u]) continue;
for (const [v, w] of g[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
let lo = 0, hi = pq.length;
while (lo < hi) { const m = (lo + hi) >> 1; pq[m][0] < dist[v] ? lo = m + 1 : hi = m; }
pq.splice(lo, 0, [dist[v], v]);
}
}
}
// Count restricted paths with DP, nodes in increasing dist order
const ways = new Array(n + 1).fill(0n);
ways[n] = 1n;
const order = [...Array(n).keys()].map(i => i + 1).sort((a, b) => dist[a] - dist[b]);
for (const u of order)
for (const [v, w] of g[u])
if (dist[u] > dist[v]) ways[u] = (ways[u] + ways[v]) % MOD;
return Number(ways[1] % MOD);
}int countRestrictedPaths(int n, int[][] edges) {
final int MOD = 1_000_000_007;
List<long[]>[] g = new List[n + 1]; // adjacency list
for (int i = 0; i <= n; i++) g[i] = new ArrayList<>();
for (int[] e : edges) {
g[e[0]].add(new long[]{e[1], e[2]});
g[e[1]].add(new long[]{e[0], e[2]});
}
// Dijkstra from node n: dist[x] = shortest distance to n
long[] dist = new long[n + 1];
Arrays.fill(dist, Long.MAX_VALUE);
dist[n] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.add(new long[]{0, n});
while (!pq.isEmpty()) {
long[] top = pq.poll();
long d = top[0]; int u = (int) top[1];
if (d > dist[u]) continue;
for (long[] e : g[u]) {
int v = (int) e[0]; long w = e[1];
if (d + w < dist[v]) { dist[v] = d + w; pq.add(new long[]{dist[v], v}); }
}
}
// Count restricted paths with DP, nodes in increasing dist order
long[] ways = new long[n + 1];
ways[n] = 1;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i + 1;
Arrays.sort(order, (a, b) -> Long.compare(dist[a], dist[b]));
for (int u : order)
for (long[] e : g[u]) {
int v = (int) e[0];
if (dist[u] > dist[v]) ways[u] = (ways[u] + ways[v]) % MOD;
}
return (int) (ways[1] % MOD);
}int countRestrictedPaths(int n, vector<vector<int>>& edges) {
const long long MOD = 1e9 + 7;
vector<vector<pair<int,int>>> g(n + 1); // adjacency list
for (auto& e : edges) {
g[e[0]].push_back({e[1], e[2]});
g[e[1]].push_back({e[0], e[2]});
}
// Dijkstra from node n: dist[x] = shortest distance to n
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.push({0, n});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto& [v, w] : g[u])
if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
}
// Count restricted paths with DP, nodes in increasing dist order
vector<long long> ways(n + 1, 0);
ways[n] = 1;
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i + 1;
sort(order.begin(), order.end(), [&](int a, int b){ return dist[a] < dist[b]; });
for (int u : order)
for (auto& [v, w] : g[u])
if (dist[u] > dist[v]) ways[u] = (ways[u] + ways[v]) % MOD;
return (int)(ways[1] % MOD);
}Explanation
The key insight is that a restricted path may only move to a neighbor that is strictly closer to the last node n. So we first need the shortest distance from n to every node, and then we count downhill paths from 1 to n.
Step 1 — Dijkstra. Run Dijkstra starting at node n to compute dist[x] = distanceToLastNode(x) for every node. We use a min-priority-queue keyed on the tentative distance and relax each edge once it is popped.
Step 2 — direct the edges. The condition dist[zi] > dist[zi+1] turns every usable edge into a one-way arc pointing from the farther endpoint to the closer one. Edges whose endpoints are equidistant from n can never be used, so they are dropped. The result is a directed acyclic graph (a DAG), because distance strictly decreases along every arc.
Step 3 — count paths in the DAG. Let ways[x] be the number of restricted paths from x to n, with ways[n] = 1. Processing nodes in increasing order of dist guarantees that whenever we look at an arc u → v (so dist[u] > dist[v]), ways[v] is already final. We accumulate ways[u] += ways[v] for every such neighbour, taking the sum modulo 109+7.
The answer is ways[1]. For the sample, node 1 can reach n = 5 through three distinct strictly-decreasing routes, so the result is 3.