Problem Statement

Package Delivery Predecessors The country of Hackerland has graph_nodes cities, numbered from 1 to graph_nodes , connected by graph_edges bidirectional roads of various lengths. The road network is connected, so every city can be reached from every other city. All international packages arrive at the capital city c . From the capital, a package addressed to some city is carried to it along any one of the shortest routes between the capital and that city, where the length of a route is the sum of the lengths of the roads it uses. For every city i , determine how many cities may have been visited on the way while delivering a package from the capital c to city i . In other words, count the cities that lie on at least one shortest route from c to i . The capital city c itself and the destination city i itself are never counted. In particular, the answer for the capital city is always 0 , and the answer for a city joined to the capital by a shortest route consisting of a single road is 0 a