P2099 [第三章习题7.3]John's trip
描述
John有很多朋友住在不同的街,John想去访问每位朋友,同时希望走的路最少。因为道路很窄,John在一条路上不能往回走。John希望从家里出发,拜访完所有的朋友后回到自己的家,且总的路程最短。John意识到如果可以每条道路都只走一次然后返回起点应该是最短的路径。写一个程序帮助John找到这样的路径。给出的每条街连接两个路口,最多有1995条街,最多44个路口。街编号由1到n, 路口分别编号1到m.
输入
多组数据。
每组数据有多行,每行由三个整数组成:x,y,z. z为这条街的编号,x和y表示这条街连接的两个路口的编号。(实际数据中可能是自环).
对于每组数据,John住在一个输入块中第一行中连接的两个顶点中编号较小的路口处。所有的街都可以连通到其他街上。“0 0”表示一个数据块的结束。再一个0 0 表示输入的结束
每组数据有多行,每行由三个整数组成:x,y,z. z为这条街的编号,x和y表示这条街连接的两个路口的编号。(实际数据中可能是自环).
对于每组数据,John住在一个输入块中第一行中连接的两个顶点中编号较小的路口处。所有的街都可以连通到其他街上。“0 0”表示一个数据块的结束。再一个0 0 表示输入的结束
输出
如果能找到所有街道遍历一次的回路,输出找到的路径,如果不存在,输出“Round trip does not exist.”
样例输入
1 2 1
2 3 2
3 1 6
1 2 5
2 3 3
3 1 4
0 0
1 2 1
2 3 2
1 3 3
2 4 4
0 0
0 0
样例输出
1 2 3 5 4 6 Round trip does not exist.