Lengths for Roads Under Repair

Hard

A region has n towns numbered 0 to n - 1 and two-way roads roads[i] = [a, b, w] between towns a and b. If w > 0, it is the length of a finished road and cannot be changed. If w = -1, the road is under repair and you choose its length: an integer from 1 to 2·10⁹. A length of 2·10⁹ means the road is effectively closed. Choose the lengths so that the shortest distance from town start to town finish becomes exactly distance. There are usually many ways, so return a specific one: 1. Take the smallest k ≥ 0 for which the goal is reachable while every road under repair stays closed except the first k of them in list order. 2. Of those k roads, the first k - 1 get length 1, and the k-th gets the one length that makes the distance exactly distance. All other roads under repair get 2·10⁹. Return all roads in their original order, with the lengths filled in. If the distance cannot be made exactly distance, return an empty list.

Example 1

n=4, roads=[[0, 1, -1], [1, 3, -1], [0, 2, 3], [2, 3, 4]], start=0, finish=3, distance=5 → [[0, 1, 1], [1, 3, 4], [0, 2, 3], [2, 3, 4]]

Without the roads under repair, the path 0 → 2 → 3 has length 7, more than 5. Opening only road 0–1 is not enough, as 1 does not reach 3 yet. So the first two open: road 0–1 gets length 1, and road 1–3 gets the smallest length, 4, that makes 0 → 1 → 3 exactly 5.

Example 2

n=3, roads=[[0, 1, 2], [1, 2, -1], [0, 2, 3]], start=0, finish=2, distance=4 → []

The finished road 0–2 already gives distance 3 < 4, and no repair can make it longer, so the answer is empty.

Example 3

n=3, roads=[[0, 1, -1], [1, 2, 6], [0, 2, 5]], start=0, finish=2, distance=5 → [[0, 1, 2000000000], [1, 2, 6], [0, 2, 5]]

The distance is already 5, so k = 0: the road under repair stays closed and gets length 2·10⁹.

Constraints

1 ≤ n ≤ 100
1 ≤ len(roads) ≤ n·(n − 1)/2
roads[i] = [a, b, w], 0 ≤ a, b < n, a ≠ b
w = -1 or 1 ≤ w ≤ 10⁷
0 ≤ start, finish < n, start ≠ finish
1 ≤ distance ≤ 10⁹
The towns are all connected, and two towns share at most one road

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Shortest Path Heap (Priority Queue)