Loading...
Loading...
Loading...
A company has n towns joined by m two-way roads "a b w" with positive cost w. Every town can reach every other town. A warehouse will be built in one town. Choose the town where the sum of the lowest travel costs to all other towns is smallest. If several towns tie, choose the smallest number. Print the town and that sum.
Example
Input
4 3 1 2 1 2 3 1 3 4 1
Output
2 4
Town 2: 1 + 1 + 2 = 4. Town 3 gives the same sum, so the smaller town wins.
Try the problem first. Open one hint at a time.
With at most 80 towns, compute the lowest cost between every pair of towns.
Floyd-Warshall does this in three loops, with the middle town in the outer loop.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor