题目内容

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

输入描述

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

题解

题目描述

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

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