crossings intersections numbered from 0 to crossings - 1, joined by two-way streets: streets[i] = [a, b, t] means the street between a and b takes t minutes to drive in either direction. Any two intersections share at most one street, and every intersection can be reached from every other.
A courier leaves intersection 0 and wants to reach intersection crossings - 1 as quickly as possible. Count how many different routes take the minimum possible time. Two routes are different if they pass through a different sequence of intersections.
The answer can be huge, so return it modulo 10⁹ + 7.crossings=4, streets=[[0, 1, 3], [1, 3, 2], [0, 2, 1], [2, 3, 4], [1, 2, 2]] → 3
The fastest trip takes 5 minutes, and three routes achieve it: 0 → 1 → 3 (3 + 2), 0 → 2 → 3 (1 + 4) and 0 → 2 → 1 → 3 (1 + 2 + 2).
crossings=3, streets=[[0, 1, 4], [1, 2, 4], [0, 2, 9]] → 1
Going through crossing 1 takes 8 minutes and the direct street takes 9, so there is a single fastest route.
crossings=1, streets=[] → 1
Start and finish are the same crossing: staying put is exactly one way.
crossings ≤ 200crossings - 1 ≤ streets.length ≤ crossings · (crossings - 1) / 2streets[i] = [a, b, t] with 0 ≤ a, b < crossings and a ≠ bt ≤ 10⁹crossings=4, streets=[[0, 1, 3], [1, 3, 2], [0, 2, 1], [2, 3, 4], [1, 2, 2]]
3
Run checks the first 3 tests in your browser. Submit checks all 61 tests on the server, hidden ones included.