1082. K Shortest Routes
A courier network has n hubs numbered 0 to n-1 and one-way lanes edges[i] = [u, v, w], meaning a van can drive from u to v in w minutes. A route from src to dst is a sequence of lanes in which each lane starts where the previous one ended. Hubs and lanes may be reused, so a network with a cycle has infinitely many routes. Two routes are different when their lane sequences differ, so parallel lanes count separately. If src == dst, the empty route of length 0 counts as a route.
Return the travel times of the k fastest routes from src to dst in non-decreasing order, listing equal times as often as there are routes with that time. If fewer than k routes exist, return all of them (possibly an empty array).
Example 1
- Input:
- n = 5edges = [[0,1,2],[0,2,5],[1,2,1],[1,3,4],[2,3,2],[3,4,3]]src = 0dst = 4k = 3
- Output:
- [8,9,10]
- Explanation:
The network has no cycles and exactly three routes from 0 to 4, taking 2+1+2+3 = 8, 2+4+3 = 9 and 5+2+3 = 10.
Example 2
- Input:
- n = 3edges = [[0,1,3],[1,0,1],[1,2,2]]src = 0dst = 2k = 4
- Output:
- [5,9,13,17]
- Explanation:
The direct route takes 5; every extra trip around the loop 0 -> 1 -> 0 adds 3 + 1 = 4, giving 5, 9, 13 and 17.
Example 3
- Input:
- n = 2edges = [[0,1,4],[1,0,3]]src = 0dst = 0k = 3
- Output:
- [0,7,14]
- Explanation:
Staying put is the empty route of length 0; after that each full loop between the hubs adds 7.
Constraints
1 ≤ n ≤ 20000
0 ≤ edges.length ≤ 60000, 0 ≤ u, v < n, 1 ≤ w ≤ 106
0 ≤ src, dst < n, 1 ≤ k ≤ 10
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 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(k * (n + m) * log(k * m))
- Space
- O(n + k * m)