题解

题面描述

给定一个地铁线路网络，其中有$N$个站点（$3 \le N \le 20$）以及各个相邻站点之间的乘坐时间。输入中：

• 第一行为站点总数$N$；
• 第二行为乘客的出发站$s$和到达站$t$；
• 接下来的若干行每行给出两个站点和它们之间的乘坐时间，输入持续到出现结束符$"0000"$为止。

本题中地铁网络被视为无向图，即每条输入的边可以双向使用。保证输入中起点与终点之间存在唯一一条耗时最短的路径。要求程序输出由各站点名称组成、以空格分隔的完整最短路径线路。

题目内容

大湾区某城市地铁线路非常密集，乘客很难一眼看出选择哪条线路乘型比较合适，为了解决这个问题，地铁公司希望你开发一个程序帮助乘客挑选合适的乘坐线路，使得乘坐时间最短，地铁公司可以提供的数据是各相邻站点之间的乘坐时间。

输入描述

第一行:$N$，站点总数,$3<=N<=20$.

第二行:乘客的出发和到达站点。

第三行起:相邻站点之间的乘坐时间，每对站点一行，站点名称是单个小写字母，站点名一定包括出发和到达站点，输入保证只有一个唯一解;

结束行:$0000$

输出描述

耗时最短的线路

样例1

输入

12
a e
a b 2
b c 2
c d 2
d e 2
f b 3
b g 3
g h 2
h i 3
j h 2 
h e 3
e k 2
k l 4
0000

输出

a b c d e

说明

输入对应的地铁图如下:

线路а->b->c->d->e耗时最短

样例2

输入

12
f k
a b 2
b c 2
c d 2
d e 2
f b 3
b g 3
g h 2
h i 3
j h 2
h e 3
e k 2
k l 4
0000

输出

f b c d e k

说明

输入对应的地铁图如下:

f->b->c->d->e->K是耗时最短的线路