Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Enjoyable Commutation
Description Isaac is tired of his daily trip to his office, using the same shortest route everyday. Although this saves his time, he must see the same scenery again and again. He cannot stand such a boring commutation any more. One day, he decided to improve the situation. He would change his route everyday at least slightly. His new scheme is as follows. On the first day, he uses the shortest route. On the second day, he uses the second shortest route, namely the shortest except one used on the first day. In general, on the You are invited to help Isaac, by writing a program which finds his route on the Input The input consists of multiple datasets, each in the following format.
Every input item in a dataset is a non-negative integer. Two or more input items in a line are separated by a space.
The y with the length _{i}d (1 ≤ _{i}i ≤ m). Both x and _{i}y are between 1 and _{i}n, inclusive. d is between 1 and 10000, inclusive. You can directly go from _{i}x to _{i}y, but not from _{i}y to _{i}x unless an edge from _{i}y to _{i}x is explicitly given. The edge connecting the same pair of nodes is unique, if any, that is, if _{i}i ≠ j, it is never the case that x equals _{i}x and _{j}y equals _{i}y. Edges are not connecting a node to itself, that is, _{j}x never equals _{i}y. Thus the inequality 0 ≤ _{i}m ≤ n(n − 1) holds.Note that the given graph may be quite unrealistic as a road network. Both the cases The last dataset is followed by a line containing five zeros (separated by a space). Output For each dataset in the input, one line should be output as specified below. An output line should not contain extra characters such as spaces. If the number of distinct paths from If the number of distinct paths from In this problem the term - The length of
*P*is less than the length of*Q*. The length of a path is defined to be the sum of lengths of edges on the path. - The length of
*P*is equal to the length of*Q*, and*P*’s sequence of node numbers comes earlier than*Q*’s in the dictionary order. Let’s specify the latter condition more precisely. Denote*P*’s sequence of node numbers by*p*_{1},*p*_{2}, …,*p*, and_{s}*Q*’s by*q*_{1},*q*_{2}, …,*q*._{t}*p*_{1}=*q*_{1}=*a*and*p*=_{s}*q*=_{t}*b*should be observed. The sequence*P*comes earlier than*Q*in the dictionary order, if for some*r*(1 ≤*r*≤*s*and*r*≤*t*),*p*_{1}=*q*_{1}, …,*p*_{r}_{ − 1}=*q*_{r}_{ − 1}, and*p*<_{r}*q*(_{r}*p*is numerically smaller than_{r}*q*)._{r}
A path visiting the same node twice or more is not allowed. Sample Input 5 20 10 1 5 1 2 1 1 3 2 1 4 1 1 5 3 2 1 1 2 3 1 2 4 2 2 5 2 3 1 1 3 2 2 3 4 1 3 5 1 4 1 1 4 2 1 4 3 1 4 5 2 5 1 1 5 2 1 5 3 1 5 4 1 4 6 1 1 4 2 4 2 1 3 2 1 2 1 1 4 3 2 3 1 3 4 1 3 3 5 1 3 1 2 1 2 3 1 1 3 1 0 0 0 0 0 Sample Output 1-2-4-3-5 1-2-3-4 None Hint In the case of the first dataset, there are 16 paths from the node 1 to 5. They are ordered as follows (The number in parentheses is the length of the path).
Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator