CT054
Message Propagation Time
HardAcceptance: 0.0%
A network consists of nodes labeled 0 to n. You are given a list of edges (a, b, t) describing the time t in seconds for a message to be sent from node a to node b. When a node receives a message, it immediately passes it on. Assuming all nodes are connected, determine how long it will take for every node to receive a message that begins at node 0. Input: first line n and m (nodes and edges), then m lines "a b t". Output: maximum time for all nodes to receive.
Example 1:
Input: 5 7
0 1 5
0 2 3
0 5 4
1 3 8
2 3 1
3 5 10
3 4 5
Output: 9
Example 2:
Input: 2 1
0 1 10
Output: 10
Constraints:
1 <= n <= 10^4 1 <= m <= 10^5 1 <= t <= 10^4 All edge weights non-negative
Tags:
graph dijkstra shortest-path heap
Loading...
Test Cases:No test cases
No test cases available.