Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
Firstly, check that it’s actually possible to make the shortest path from source to destination equal to the target.
If the shortest path from source to destination without the edges to be modified, is less than the target, then it is not possible.
If the shortest path from source to destination including the edges to be modified and assigning them a temporary weight of 1, is greater than the target, then it is also not possible.
Suppose we can find a modifiable edge (u, v) such that the length of the shortest path from source to u (dis1) plus the length of the shortest path from v to destination (dis2) is less than target (dis1 + dis2 < target), then we can change its weight to “target - dis1 - dis2”.
For all the other edges that still have the weight “-1”, change the weights into sufficient large number (target, target + 1 or 200000000 etc.).