5260：行路难

题目描述

度度熊非常仰慕诗仙太白。这一天，它决定追寻仙人的踪迹，找到沧海中仙山之所在。

沧海之中有很多个岛屿，由于这些岛屿都和诗仙有一种神奇而莫名的关系，当你在一个岛屿上默念一句诗时，就会传送到另一个岛屿上去。度度熊现在在岛屿A上，它希望通过默念一系列诗句，能够被传送到岛屿B上。

如果可以，它还希望这些诗句连起来，字典序可以最小。此言尤美，是邪？

输入解释

第一行一个整数T，表示T组数据。

每组数据的第一行包含四个整数$N (2 \leq N \leq 50), M (0 \leq M \leq 500)$，A，B。表示N个岛屿，和M个神奇的诗句传送方法，以及度度熊的起点和目的地$(0 \leq A, B < N, A \ne B)$。

然后的M行，每行两个数字$s, t (0 \leq s, t < N)$和一个字符串S（字符串只包含小写字母，$1 \leq S的长度 \leq 6$)，表示默念S可以从s传送到t，注意s和t可以相同。并且可能有多种传送方法从一个岛屿到另一个岛屿，另外，如果在一个岛屿上默念一句诗可以传送到多个岛屿上，你可以随心，选择任意一个。

输出解释

对于每组测试数据输出两行：

第一行输出"Case #i:"，其中 I 代表第 I 组测试数据。

然后输出可以完成传送的方法连接起来后字典序最小的传送诗句，如果不存在，无论是不存在字典序最小的，还是不存在这样的传送方法，都输出"Tough way!"（没有引号）。

输入样例

3
2 2 0 1
0 0 b
0 1 a
2 2 0 1
0 0 a
0 1 b
4 4 0 1
0 3 hi
0 2 hey
3 1 rishi
2 1 jude

输出样例

Case #1:
a
Case #2:
Tough way!
Case #3:
heyjude

提示

对于样例2，可以无限的利用a使字典序更小。

来自杭电HDUOJ的附加信息

Recommend

hujie

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2015年百度之星程序设计大赛 - 复赛

源链接： HDU-5260

最后修改于 2020-10-25T23:21:08+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
6000/3000MS(Java/Others)	32768/32768K(Java/Others)