Loading...
Loading...
Loading...
A food delivery app near a college works with n areas, numbered 1 to n. Its riders use one-way roads, and each road takes a fixed number of minutes to ride.
All orders start from the kitchen in area s. For every area from 1 to n, print the smallest total time to ride there from area s. The time to area s itself is 0. If an area cannot be reached at all, print -1 for it.
int limit, so use longExample 1
Input
4 5 1 2 4 1 3 1 3 2 2 2 4 5 3 4 8 1
Output
0 3 1 8
Area 2 is faster through area 3 (1 + 2 = 3) than directly (4). Area 4 is then 3 + 5 = 8, better than 1 + 8 = 9.
Example 2
Input
3 2 1 2 5 3 2 1 3
Output
-1 1 0
From area 3 a rider reaches area 2, but the road between 1 and 2 only goes from 1, so area 1 cannot be reached.
Try the problem first. Open one hint at a time.
With equal road times, a plain level-by-level search would work. Different times break that, because more roads can still mean less time.
Keep a best-known time for every area. Always continue from the area with the smallest known time that is not finished yet.
A PriorityQueue of {time, area} pairs gives the smallest time quickly. When you take an area out with a time larger than its best, skip it.
From a finished area, try every road out of it and improve the time of the area at the other end. Store times as long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor