
ZOJ Problem Set  2827
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 kth day, the kth shortest route is chosen. Visiting the same place twice on a route should be avoided, of course. You are invited to help Isaac, by writing a program which finds his route on the kth day. The problem is easily modeled using terms in the graph theory. Your program should find the kth shortest path in the given directed graph. Input The input consists of multiple datasets, each in the following format.
Every input item in a dataset is a nonnegative integer. Two or more input items in a line are separated by a space. n is the number of nodes in the graph. You can assume the inequality 2 �� n �� 50. m is the number of (directed) edges. a is the start node, and b is the goal node. They are between 1 and n, inclusive. You are required to find the kth shortest path from a to b. You can assume 1 �� k �� 200 and a �� b. The ith edge is from the node x_{i} to y_{i} with the length d_{i} (1 �� i �� m). Both x_{i} and y_{i} are between 1 and n, inclusive. d_{i} is between 1 and 10000, inclusive. You can directly go from x_{i} to y_{i}, but not from y_{i} to x_{i} unless an edge from y_{i} to x_{i} is explicitly given. The edge connecting the same pair of nodes is unique, if any, that is, if i �� j, it is never the case that x_{i} equals x_{j} and y_{i} equals y_{j}. Edges are not connecting a node to itself, that is, x_{i} never equals y_{i}. Thus the inequality 0 �� m �� n(n − 1) holds. Note that the given graph may be quite unrealistic as a road network. Both the cases m = 0 and m = n(n − 1) are included in the judges�� data. 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 a to b is less than
k, the string If the number of distinct paths from a to b is k or more, the node numbers visited in the kth shortest path should be printed in the visited order, separated by a hyphen (minus sign). Note that a must be the first, and i must be the last in the printed line. In this problem the term shorter (thus shortest also) has a special meaning. A path P is defined to be shorter than Q, if and only if one of the following conditions holds.
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 12435 1234 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: Asia Regional Contest, Yokohama, 2006 