War - Escape Part 2
Time limit2sMemory limit128 MB
Given a weighted graph, find the shortest path from city 1 to city N after removing every edge that lies on any shortest path between them.
- Level
Medium7 of 10
- Topics
- Shortest path, Graph, Implementation
- Solved
- No attempts yet
Problem
The war is nearing its end, and your army has advanced all the way to city 1, the enemy capital. Just as you are preparing the final attack, you discover that the easy advance was a trap.
You decide to turn the army back and retreat to city N, the border city, to regroup. The enemy knows the local geography well and expects your army to retreat along one of the shortest routes.
Therefore, every road that can appear in at least one shortest route is considered dangerous because the enemy may ambush it. Given the roads between cities, find the shortest travel time from city 1 to city N while avoiding all dangerous roads.
Input
The first line contains the number of cities N (1 <= N <= 1,000) and the number of roads M (0 <= M <= 5,000).
Each of the next M lines contains three integers a, b, and c. This means there is a bidirectional road between city a and city b, and traveling along that road takes c time.
Output
Print the shortest travel time from city 1 to city N after avoiding every road that the enemy may ambush.