题解

题目描述

已知 A 市运营了 $N$ 条地铁线路，市民在乘坐地铁时单条线路通票 2 元，换乘一次加 1 元。给出 $N$ 条线路的所有站名列表，请帮乘客寻找从出发站到目的站最便宜的地铁换乘方案，并输出票价。每条地铁线路不包含环路（即没有相同站名）。不同线路中相同的站点名表示可以在该站点换乘。输入保证若可达则唯一解。

• 输入
  • 第一行：地铁线路个数 $N$，范围 $[1,1000]$
  • 接下来的 $N$ 行：第 $i$ 条线路依次包含的站名（站名间用空格分隔，每个站名长度 $\le100$，每条线路站点数 $\le100$）
  • 第 $N+2$ 行：出发站和目的站，用空格分隔

题目内容

已知 $A$ 市运营了 $N$ 条地铁线路，市民在乘坐地铁时单条线路通票 $2$ 元，换乘一次加 $1$ 元。给出 $N$ 条线路的所有站名列表，请帮乘客寻找从出发站到目的站最便官的地铁换乘方案，并输出票价。每条地铁线路不包含环路，即没有相同站名。

输入描述

第一行为地铁线路个数 $N$ ，范围是 $[1,1000]$；

第二行 到 $N+1$ 行：每条线路依次包含的站名，每个站名包含的字符个数不超过 $100$ ，站点个数也不超过 $100$ ，依次用空格隔开，不同线路中相同的站点名表示是一个换乘站；

第 $N+2$ 行，出发站和目的站，用空格隔开。

输入保证：若可达则为唯一解。

输出描述

第一行按照出发站-换乘站(可以是多个)-目的站的格式输出换乘方案的字符串;

第二行输出换乘方案的总票价。

如果没有任何方案可实现出发站到目的站，只输出一行： $NA$ 。

样例1

输入

3
A B C D F
C E G H
B G I J
A J

输出

A-B-J
3

说明

从出发站 $A$ 到目的站 $J$ 有两个方案：一号线到 $C$ 站后换乘二号线，到 $G$ 站后换乘三号线到 $J$ 站，换乘两次，总票价 $4$ 元；一号线到 $B$ 站后换乘三号线到 $J$ 站，换乘一次，总票价 $3$ 元。因此按照第二个方案愉出。

样例2

输入

3
A B C D F
E G H
G I J
A J

输出

NA

说明

从出发站 $A$ 所在的一号线没有任何一个换乘站可以到二号线和三号线，因此没有方案抵达目的站 $J$ ，输出 $NA$ 。