1550. [CEOI1997]参观洞穴

【题目描述】

Byteland有很多洞穴，其中一个如图所示。

该洞穴有一些有趣的特点：

1：所有的房间和通道在同一层且任意两条通道不交叉。

2：其中一些房间组成一个圆圈的形状，这些房间称做外房间，其余房间都在外房间组成的圆圈里面，所有这些房间称为内房间。洞穴的惟一入口（同时也是惟一出口）直接通向其中一个外房间。

3：从每个房间出发，恰好有三条通道通往另外三个不同的房间。显然，从每个外房间出发的三条通道分别通往它在圆圈上两个相邻的外房间和某个内房间。

4：外房间组成的圆圈上的通道称做外通道，所有其他通道称做内通道。

5：对于每个房间来说，我们都能找到一条通往任意一个其他房间的只经过内通道的路线，但是如果我们规定每个内通道只能走一次的话，这样的路线是惟一的。

6：不是所有通道都好走。我们把通道分为两种：好走的通道和难走的通道。

Byteland政府决定把这个有趣的洞穴改造成一个风景区供游客参观。为了方便管理，政府决定事先给游客规定一条参观线路，每个房间参观一次（除了路线起始和终止房间——它被参观了两次）。为了让游客更加满意，预定的这条路线中，难走的通道数目要尽量少。

【输入格式】

输入文件的第一行有两个整数n,k，其中3<=n<=500，n是房间数目，k是外房间数目，k>=3.房间被标号为1到n。1号房间是出入口。1,2,...,k号房间是外房间。它们不必在圆圈上以这个顺序排列。

接下来的3n/2行描述了通道。每一行有三个由空格分隔的整数a,b,c。a和b是一条通道的两个端点。c是0或1,0意味着这是一条好走的通道，1意味着这是一条难走的通道。

【输出格式】

输出一行n个正整数，代表最佳路线先后访问的房间序列。这个序列必须从1开始。

【样例输入】

8 5

1 3 0

3 2 0

7 3 1

7 2 0

8 7 0

1 8 0

6 8 0

6 4 0

6 5 1

5 4 0

2 4 0

5 1 0

【样例输出】

1 5 4 6 8 7 2 3

【来源】

CEOI 1997 The Cave

POJ 1714

刘汝佳，《算法艺术与信息学竞赛》，P289 例题4