A town is a weighted undirected graph of n squares (numbered 0 to n-1) joined by m streets, each with a positive integer length. A route is a path that starts at square s, ends at square t, and never revisits a square.
Among all routes from s to t, consider those whose total length equals the minimum possible (the shortest-path distance from s to t). Count how many such minimum-length routes exist, and report the count modulo 1000000007. If t is unreachable from s, the count is 0. If s equals t, there is exactly one route (the empty route), so the count is 1.
Because all street lengths are positive, every minimum-length route is automatically a simple path (no repeated square).
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a street between squares u and v of length w.
Final line: two integers s t.
A single integer: the number of distinct shortest (minimum-total-length) routes from s to t, modulo 1000000007.
Example 1
Input
4 4 0 1 1 0 2 1 1 3 1 2 3 1 0 3
Expected
2
Explanation
The shortest distance from 0 to 3 is 2, achieved by 0->1->3 and 0->2->3 — two distinct routes, so the count is 2.
Example 2
Input
3 2 0 1 5 1 2 5 0 2
Expected
1
Explanation
The only route from 0 to 2 is 0->1->2 (length 10), so there is exactly one shortest route.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →