bzoj#P2183. Pku3137 Enjoyable Commutation

Pku3137 Enjoyable Commutation

题目描述

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 kk-th day, the kk-th 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 kk-th day. The problem is easily modeled using terms in the graph theory. Your program should find the kk-th shortest path in the given directed graph.

nn 结点有向简单图中的简单 kk 短路(结点不能重复经过)。路径长度相同时按照字典序排列。

输入格式

The input consists of multiple datasets, each in the following format.

n  m  k  a  bn\quad\; m\quad\; k\quad\; a\quad\; b

x1y1d1x_1\quad y_1\quad d_1

x2y2d2x_2\quad y_2\quad d_2

\quad \quad \dots

xmymdmx_m\quad y_m\quad d_m

Every input item in a dataset is a non-negative integer. Two or more input items in a line are separated by a space.

nn is the number of nodes in the graph. You can assume the inequality 2n502\leq n\leq 50 . mm is the number of (directed) edges. aa is the start node, and bb is the goal node. They are between 11 and nn , inclusive. You are required to find the k-th shortest path from aa to bb . You can assume 1k2001 \leq k \leq 200 and aba \neq b .

The ii-th edge is from the node xix_i to yiy_i with the length di(1im)d_i (1 \leq i \leq m) . Both xix_i and yiy_i are between 11 and nn , inclusive. did_i is between 11 and 10410^4, inclusive. You can directly go from xix_i to yiy_i, but not from yiy_i to xix_i unless an edge from yiy_i to xix_i is explicitly given. The edge connecting the same pair of nodes is unique, if any, that is, if iji \neq j , it is never the case that xix_i equals xjx_j and yiy_i equals yjy_j . Edges are not connecting a node to itself, that is, xix_i never equals yiy_i . Thus the inequality 0mn(n1)0 \leq m \leq n(n − 1) holds.

Note that the given graph may be quite unrealistic as a road network. Both the cases m=0m = 0 and m=n(n1)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).

输出格式

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 aa to bb is less than kk , the string None should be printed. Note that the first letter of None is in uppercase, while the other letters are in lowercase.

If the number of distinct paths from aa to bb is kk or more, the node numbers visited in the kk-th shortest path should be printed in the visited order, separated by a hyphen (minus sign). Note that aa must be the first, and ii must be the last in the printed line.

In this problem the term shorter (thus shortest also) has a special meaning. A path PP is defined to be shorter than QQ , if and only if one of the following conditions holds.

  1. The length of PP is less than the length of QQ . The length of a path is defined to be the sum of lengths of edges on the path.
  2. The length of PP is equal to the length of QQ , and PP’s sequence of node numbers comes earlier than QQ’s in the dictionary order. Let’s specify the latter condition more precisely. Denote PP’s sequence of node numbers by p1,p2,,psp_1, p_2, \dots, p_s , and QQ’s by q1,q2,,qtq_1, q_2, \dots, q_t . p1=q1=ap_1 = q_1 = a and ps=qt=bp_s = q_t = b should be observed. The sequence PP comes earlier than QQ in the dictionary order, if for some r(1rsr (1 \leq r \leq s and rt)r \leq t), p1=q1,,pr1=qr1p_1 = q_1, \dots, p_{r − 1} = q_{r − 1} , and pr<qrp_r < q_r (prp_r is numerically smaller than qrq_r).

A path visiting the same node twice or more is not allowed.

样例输入

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

样例输出

1-2-4-3-5
1-2-3-4
None

样例说明

In the case of the first dataset, there are 1616 paths from the node 11 to 55 . They are ordered as follows (The number in parentheses is the length of the path).

              1(3)12351 (3) 1-2-3-5                         9(5)123459 (5) 1-2-3-4-5

              2(3)1252 (3) 1-2-5                                10(5)1243510 (5) 1-2-4-3-5

              3(3)1353 (3) 1-3-5                                11(5)124511 (5) 1-2-4-5

              4(3)14354 (3) 1-4-3-5                         12(5)134512 (5) 1-3-4-5

              5(3)1455 (3) 1-4-5                                13(6)132513 (6) 1-3-2-5

              6(3)156 (3) 1-5                                        14(6)1342514 (6) 1-3-4-2-5

              7(4)142357 (4) 1-4-2-3-5                  15(6)14325 15 (6) 1-4-3-2-5

              8(4)14258 (4) 1-4-2-5                         16(8)13245 16 (8) 1-3-2-4-5

数据规模与约定

对于 100%100\% 的数据,n50n\leq50k200k\leq 200

题目来源

Japan 2006 K短路