A relay network has n nodes (numbered 0 to n-1) joined by one-way links, each taking a positive integer number of ticks to carry a signal from its start node to its end node.
At tick 0, TWO beacons at nodes a and b broadcast simultaneously. A node receives the signal at the earliest tick any copy (from either beacon, along any path) reaches it; nodes a and b themselves are received at tick 0. Report the tick at which the last node is covered — the maximum over all nodes of the earliest arrival time. If some node is never reached from either beacon, report that the network is not fully covered.
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a one-way link from u to v taking w ticks.
Final line: two integers a b, the two broadcasting nodes.
A single integer: the tick when every node has been covered, or -1 if some node is never reached.
Example 1
Input
4 3 0 1 5 2 3 5 2 1 1 0 2
Expected
5
Explanation
From beacon 0: node1 at 5. From beacon 2: node3 at 5, node1 at 1. Each node's earliest: node0=0, node1=1, node2=0, node3=5. The last covered is at tick 5.
Example 2
Input
3 1 0 1 4 0 0
Expected
-1
Explanation
Both beacons are at node 0. Node 1 is covered at tick 4, but node 2 has no incoming link and is never reached, so the network is not fully covered: -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 →