Loading
Loading
An emergency alert network has n relay stations numbered 1 to n. Each entry [from, to, ms] in links is a one-way link: a message at from reaches to after ms milliseconds.
An alert is issued at station source at time 0 and every station forwards it along all its links immediately. Return the time at which the last station receives it, or -1 if some station never does.
n = 4, links = [[1,2,4],[1,3,1],[3,2,2],[2,4,3]], source = 1station 1 at 0the alert starts herestation 3 at 1direct link, 1 msstation 2 at 3via 3 (1 + 2) beats the direct 4 msstation 4 at 6via 2 (3 + 3) — the last to hear6Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 1 | 2 | 4 |
|---|---|---|---|
| 1 | 1 | 3 | 1 |
| 2 | 3 | 2 | 2 |
| 3 | 2 | 4 | 3 |
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(links log links) time · O(n + links) space
Input. Run your code to watch it work on this input, one line at a time.
| 0 | 1 | 2 | 4 |
|---|---|---|---|
| 1 | 1 | 3 | 1 |
| 2 | 3 | 2 | 2 |
| 3 | 2 | 4 | 3 |
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
Example 2
| 0 | 1 | 2 | 5 |
|---|---|---|---|
| 1 | 2 | 1 | 5 |
Nothing ever reaches station 3.
Example 3