Codeforces Round #287 Problem E - Breaking Good

Problem Statement:
507E - Breaking Good

Solution:
[Off topic: btw, Breaking Bad is damn awesome!]
This problem employs an interesting trick using Dijkstra Algorithm, which is quite intuitive to discover.

First suppose there are no broken roads, i.e. every edges are valid edges. In this case, we can simply run a BFS to find the shortest path between node 1 (city) and node N (headquarter), and for all other roads not in this path, we just blow them up. However, in the problem, we can have roads which must be repaired before it can be used. Hence naturally BFS is not applicable to this case anymore and we need something else to account for the cost of repairing a road. Yet, we also need the property that the shortest path will still have the same length as the ones that are produced if we are to run BFS.