Loading...
Loading...
Loading...
A student runs a weekend parcel service between n hubs, numbered 1 to n. The hubs are joined by m one-way roads. Each road has a cost in rupees: fuel minus any sponsor bonus on that road. A big bonus can make the cost negative.
The roads never form a loop whose total cost is below 0, so riding in circles never earns money.
For every pair of hubs i and j, find the smallest total cost to go from i to j. The cost from a hub to itself is 0. Print the whole table, and print NO where hub j cannot be reached from hub i.
NO if there is no route.int range, so use longExample 1
Input
4 5 1 2 4 2 3 -2 1 3 5 3 4 3 4 1 1
Output
0 4 2 5 2 0 -2 1 4 8 0 3 1 5 3 0
From hub 1, hub 3 costs 4 + (-2) = 2 through hub 2, cheaper than the direct road for 5. Then hub 4 costs 2 + 3 = 5. The loop 1 → 2 → 3 → 4 → 1 costs 6, which is not below 0.
Example 2
Input
3 1 2 3 -7
Output
0 NO NO NO 0 -7 NO NO 0
The only road goes from hub 2 to hub 3. Every other pair of different hubs has no route.
Try the problem first. Open one hint at a time.
Start a table d with 0 on the diagonal, the cheapest direct road where one exists, and a very large value elsewhere.
Now allow hubs as middle points one at a time. When hub via is allowed, a route i → via → j may beat the best i → j found so far.
The loop over via must be the outermost of the three loops. Then every route through hubs 1 to via is already counted when via moves on.
Skip a pair when either half is still the very large value. With negative costs, "large plus negative" looks like a real route.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor