A mesh of n sensors (numbered 0 to n-1) is wired by one-way signal links, each taking a positive integer number of milliseconds to carry a ping from its start sensor to its end sensor.
At time 0, sensor s emits a ping. The ping travels along every outgoing link simultaneously, and a sensor is considered to have received the ping the moment the earliest-arriving copy reaches it. Report the time at which the LAST sensor receives the ping (that is, the maximum over all sensors of the earliest arrival time). If at least one sensor never receives the ping, report that the mesh does not fully settle.
Line 1: three integers n, m, and s.
Each of the next m lines: three integers u v w, a one-way link from sensor u to sensor v taking w milliseconds.
A single integer: the time when all sensors have received the ping, or -1 if some sensor never does. (If n is 1 the answer is 0.)
Example 1
Input
4 4 0 0 1 2 1 2 1 0 3 4 2 3 5
Expected
4
Explanation
Earliest arrivals from 0: sensor1=2, sensor2=3, sensor3=4 (the direct 0->3 of 4 beats 0->1->2->3=8). The last to receive is at time 4.
Example 2
Input
3 1 0 0 1 4
Expected
-1
Explanation
Sensor 2 has no incoming link and never receives the ping, so the mesh does not fully settle: -1.
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 →