Count Restricted Paths to the Exit Node
In a weighted service mesh, a path from the entry node to the exit node is 'restricted' if each hop strictly decreases the remaining shortest-distance to the exit. Count such monotone paths.
Problem
Given an undirected weighted graph with n nodes (1-indexed) and edges [u, v, w], let dist(x) be the shortest distance from node x to node n. A restricted path starts at node 1, ends at node n, and visits nodes z1=1, z2, ..., zk=n where dist(z_i) > dist(z_{i+1}) for every step. Return the number of restricted paths modulo 1e9 + 7.
Input
An integer n and an array edges of [u, v, weight] triples.
Output
An integer: the number of restricted paths modulo 1e9 + 7.
Constraints
- 1 <= n <= 20000
- n-1 <= edges.length <= 40000
- Edge weights are positive; the graph is connected.
Examples
Example 1
Input
n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output
3
Three paths from 1 to 5 strictly decrease the distance-to-5 at every hop.
Example 2
Input
n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
Output
1
Exactly one restricted path exists.