Loading...
Loading...
Loading...
A courier moves between n towns joined by m two-way roads. A road "a b w" costs w to drive. Print the lowest total cost to go from town s to town t, or -1 if the courier cannot get there.
Example 1
Input
4 4 1 2 4 1 3 1 3 2 2 2 4 1 1 4
Output
4
Route 1, 3, 2, 4 costs 1 + 2 + 1.
Example 2
Input
3 1 1 2 5 1 3
Output
-1
Try the problem first. Open one hint at a time.
All costs are positive, so use a heap of (cost so far, town).
Skip a heap entry when its cost is larger than the best known cost for that town.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor