769. Downhill Path Count
A ferry company serves n harbors numbered 1 to n. Each entry [a, b, minutes] of edges is a two-way route between harbors a and b that takes minutes minutes. Any harbor can be reached from any other, and a pair of harbors has at most one direct route.
Let dist[x] be the least travel time from harbor x to harbor n. A downhill trip goes from harbor 1 to harbor n through consecutive harbors h0 = 1, h1, ..., hk = n joined by direct routes, such that dist[h0] > dist[h1] > ... > dist[hk]. Count the downhill trips and return the count modulo 1000000007.
Example 1
- Input:
- n = 5, edges = [[1,2,3],[1,3,4],[2,4,2],[3,4,1],[4,5,6]]
- Output:
- 2
- Explanation:
Distances to depot 5 are 11, 8, 7, 6, 0 for towns 1 to 5. The two downhill routes are 1-2-4-5 and 1-3-4-5.
Example 2
- Input:
- n = 3, edges = [[1,2,1],[2,3,1]]
- Output:
- 1
- Explanation:
A single chain 1-2-3 has distances 2, 1, 0, so exactly one downhill route exists.
Example 3
- Input:
- n = 4edges = [[1,2,2],[2,3,2],[1,3,5],[3,4,1],[2,4,10]]
- Output:
- 3
- Explanation:
The distances to town 4 are 5, 3, 1, 0. The downhill routes are 1-2-3-4, 1-2-4 and 1-3-4, so the answer is 3.
Constraints
- 2 ≤ n ≤ 2 * 104
- n - 1 ≤ edges.length ≤ 4 * 104
- 1 ≤ a, b ≤ n, a ≠ b
- 1 ≤ minutes ≤ 105
- The graph is connected and has no repeated pair of harbors.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O((n + m) log n)
- Space
- O(n + m)