题目内容

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

输入描述

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

题解

题面描述

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

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

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