A logistics company runs n sorting hubs (numbered 0 to n-1) connected by one-way conveyor links. Each link goes from one hub to another and takes a positive integer number of minutes.
Given a source hub s, compute, for every hub, the minimum number of minutes to reach it from s following links in their allowed direction. A hub that cannot be reached from s has no finite distance.
Line 1: three integers n, m, and s (the number of hubs, the number of links, and the source hub).
Each of the next m lines: three integers u v w, a one-way link from hub u to hub v taking w minutes.
One line with n space-separated tokens. Token i is the shortest distance from s to hub i, or the literal INF if hub i is unreachable. (The distance from s to itself is 0.)
Example 1
Input
4 4 0 0 1 2 1 2 3 0 2 10 2 3 1
Expected
0 2 5 6
Explanation
From 0: hub 0 is 0, hub 1 is 2, hub 2 is 5 (0->1->2 beats the direct 10), hub 3 is 6 (0->1->2->3).
Example 2
Input
3 1 0 0 1 4
Expected
0 4 INF
Explanation
From 0 you can reach hub 1 in 4 minutes, but hub 2 has no incoming route, so its distance is INF.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →