Codeforces 449B - Jzzhu and Cities

Problem Statement:
449B - Jzzhu and Cities

Solution:
An interesting graph problem. In both Bellman-Ford and Dijkstra single source shortest path algorithms, we have the concept of "relaxed" edges, in which intuitively can be viewed this way: We are given a set of balls connected together with strings. If we choose a ball as the "source" and pick it up, other balls will be hanging with some strings tight and some strings slack. The tight strings are the "relaxed" edges in single source shortest path algorithm. Those which are not relaxed can actually be removed from the shortest path graph.