网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
聪明的耗子
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | mousea.in | 输出文件 | mousea.out |
【问题描述】
在XOI总部,有一只由C.H养的耗子,这一只耗子拥有超过一般耗子的智商,而且很听话,所有XOI的人都叫它“WM”意思为聪明的耗子。而XOI总部有另一名成员X.J.H养的一只大猫,这只猫是一个捕鼠能手,名字叫“UC”。有一天C.H.和X.J.H打赌,C.H认为W.M可以逃脱U.C的追捕,X.J.H很不服气,他认为W.M是逃不过U.C的追捕。
他们就在XOI总部做了一个实验来判断,XOI总部的地形有点奇怪,如下图所示,
每一间工作室只有三条通路,而且某一些路是非常不好走的,通过的时间较长,因为那里放满了杂物,通过其余通路的用时是一样的,U.C可以以最快的速度从第一间工作室,通过所有的工作室再回到第一间工作室,而且每一间工作室只能进一次。如果W.M也可以在最短的时间内通过则U.C就算输了。事实上W.M办到了。
请问它是如何办到的?
【输入格式】
输入文件的第一行为数字3<n≤80。n为工作室的个数,接下的3n/2行为a,b,c表示为从a工作室到b工作室有通道。c为0时通道为好走的通道,为1时是难走的通道。
【输出格式】
输出文件为耗子依次通过工作室的编号。
【输入输出样例】
样例输入:(mouse.in)
8
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
样例输出(mouse.out):
1 5 4 6 8 7 2 3