1644. Time For the Signal to Reach Everyone
A signal starts at vertex s and travels along directed edges, each taking a
given non-negative time. Every vertex forwards the signal onward the moment it
arrives.
Print the time at which the LAST vertex receives it, or -1 if some vertex
never does.
Each vertex is reached at its shortest distance from s, so the answer is the
largest of those distances. The -1 case matters as much as the number: a graph
where one vertex is unreachable must not report the maximum over the rest.
Dijkstra with the heap from problem 866 is the tool. The heap answers "which unfinished vertex is nearest" over and over while distances keep improving, which is the same repeated extract-minimum, with the set changing underneath it.
Weights are non-negative here, and that is what makes finalising a vertex on first extraction safe. Problem 1641 is the same shape once that assumption is removed.
Constraints - `1 ≤ n ≤ 10000` - `0 ≤ m ≤ 50000` - `1 ≤ s ≤ n` - `0 ≤ w ≤ 10000`
Input
The first line contains three integers n, m and s.
Each of the next m lines contains three integers u, v and w: a directed edge from u to v taking time w.
Output
Print the time the last vertex receives the signal, or -1 if any vertex never receives it.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.