757. Shared Road Network
A delivery firm runs two depots, src1 and src2, and wants every parcel to reach one warehouse, dest. The region has n towns numbered 0 to n - 1. Each entry [u, v, w] of edges is a one-way road from town u to town v that costs w to build; parallel roads and loops may appear.
Choose a set of roads to build so that dest can be reached by following built roads from src1 and also from src2. A road used by both journeys is paid for only once. Return the smallest total cost, or -1 if at least one depot can never reach the warehouse. The three towns are not necessarily different.
Example 1
- Input:
- n = 5edges = [[0,2,4],[1,2,3],[2,3,2],[2,4,9],[3,4,1],[0,4,12],[1,4,10]]src1 = 0src2 = 1dest = 4
- Output:
- 10
- Explanation:
Both sources meet at town 2 (cost 4 + 3), then share the road 2 to 3 to 4 (cost 2 + 1), for a total of 10; building the direct roads instead would cost 22.
Example 2
- Input:
- n = 3edges = [[0,1,5],[2,1,1]]src1 = 0src2 = 1dest = 2
- Output:
- -1
- Explanation:
No road leads into town 2, so it cannot be reached from either source and the answer is -1.
Example 3
- Input:
- n = 4edges = [[0,1,2],[1,2,2],[3,2,1]]src1 = 0src2 = 3dest = 2
- Output:
- 5
- Explanation:
The two routes only meet at the destination: 0 to 1 to 2 costs 4 and 3 to 2 costs 1, so nothing can be shared and the total is 5.
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ edges.length ≤ 2 * 105
- edges[i] = [u, v, w] with 0 ≤ u, v < n and 0 ≤ w ≤ 106
- 0 ≤ src1, src2, dest < n
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)