How long until everyone hears
Send a signal through a one-way network with travel times and find when the last place receives it. About 13 minutes.
One-way roads, one big question
A signal starts at one place and travels along one-way links, each taking some time. You want to know when the whole network has it. The signal splits and travels every link at once, so a place hears it at the cheapest arrival time.
That's exactly the cheapest cost from the source. Run the same cheapest-first search, but build the neighbour lists in one direction only: a link from u to v adds v to u's list and nothing the other way.
adj = {0: [(1, 2), (2, 5)]}
neighbour, cost = adj[0][0]The signal starts at 0 at time 0.
The last place to hear
Once every cheapest cost is known, the network is done when the last place hears. That's the largest cost in the list.
But if some place still has a huge cost, nobody could ever tell it, so the signal never reaches everyone and the answer is -1. Check for that before taking the maximum. A network where the source is the only place has answer 0.
slowest = max(dist)
A signal source can reach 4 of the 5 places. What should the delay be?
- A-1, because one place never gets it
- BThe largest time among the 4 that heard
- C0
Show the answer
-1, because one place never gets it. The signal can never finish if even one place is cut off.
Signal delay
A network has n places, numbered 0 to n − 1. links[i] = [u, v, t] is a one-way link from place u to place v that takes t time to cross, where t is at least 1. A signal starts at place source at time 0 and travels along every link it can. Return the time at which the last place receives the signal, or -1 if some place never does.
n = 4, links = [[0, 1, 2], [0, 2, 5], [1, 2, 1], [2, 3, 2]], source = 0 → 5
1 ≤ n ≤ 100,000 · 0 ≤ links ≤ 200,000 · 1 ≤ t ≤ 1,000