Problem T
Subway Map
In the year 2120 there is a vast subway network under all of
Lund, consisting of
Erik has had enough of Skånetrafiken’s terrible route
planning software and plans to build his own. To do this, he
needs to know the length of each of the tunnels, but the subway
map is incomplete in this regard. By looking out the window,
Erik has noticed that some tunnels have special cables running
alongside them, probably for providing power to the stations.
The cables connect the stations so that every station is
connected to the central station (the station numbered
Erik knows the precise length of some tunnels, and which tunnels contain cables. Using this information he wants to find the minimum possible length for each tunnel with unknown length. Unfortunately, Erik’s algorithm isn’t efficient enough to process the enormous size of Lund’s subway network. Can you help him by implementing a more efficient algorithm?
Input
The first line of input contains two integers
It is guaranteed that there is at most one tunnel connecting
the same pair of stations, and that it is possible to travel
between any pair of stations using the subway. It is also
guaranteed that there exists a path between any station and
station number
Output
For each tunnel with
Sample Description
In the first sample case, the minimal distance for the
unknown tunnel (between stations
Sample Input 1 | Sample Output 1 |
---|---|
3 3 1 2 5 1 2 3 3 1 3 1 ? 0 |
5 |
Sample Input 2 | Sample Output 2 |
---|---|
4 3 1 2 ? 1 1 3 ? 1 2 4 ? 1 |
1 1 1 |