A relay grid is a weighted undirected graph of n nodes (numbered 0 to n-1) joined by m cables, each with a positive integer length.
The weighted diameter of the grid is the largest shortest-path distance taken over every pair of distinct nodes. Compute it. If the grid is disconnected (some pair of nodes has no connecting path), report that the diameter is undefined. If n is 1 there are no pairs, so the diameter is 0.
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a cable between nodes u and v of length w.
A single integer: the weighted diameter, or -1 if the graph is disconnected.
Example 1
Input
4 3 0 1 1 1 2 2 2 3 3
Expected
6
Explanation
This is a path 0-1-2-3. The farthest pair is 0 and 3 with distance 1+2+3=6, so the weighted diameter is 6.
Example 2
Input
3 1 0 1 4
Expected
-1
Explanation
Node 2 has no cables, so it is unreachable from nodes 0 and 1; the graph is disconnected and the diameter is -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 →