acmsguru |
---|
Finished |
Xto point
Y. The roads in the village are bidirectional and connect the pairs of junctions. Village has N junctions and M roads. Each road has some fixed length. Points
Xand
Yare junctions. The hijacker certainly chose one of the shortest routes from
Xto
Y. Your first deputy chief suggested that the criminal should be intercepted on the junction number 1, but you noticed that at the moment when the criminal could reach this junction he can actually be at one of A1 different points of the village (some of these points could be at the roads). Your second deputy chief suggested that interception should be arranged at the second junction. But you noticed again that at that time criminal could be at A2 different points of the village. The last suggestion came from N-th deputy chief, and you answered him with number AN. If the way of the criminal does not pass through the junction K for sure, AK will be equal to zero.
sample input | sample output |
6 2 5 9 1 2 1 1 3 10 1 6 1 4 6 1 6 5 1 2 6 2 3 6 1 5 3 1 4 5 1 | 2 1 0 0 1 1 |
sample input | sample output |
4 1 4 5 1 2 1 1 4 2 1 3 1 2 4 1 3 4 1 | 1 3 3 1 |
Name |
---|