P4324.【广度优先搜索5】城市交通网络中的最短换乘次数
本题为2025年10月22日华为机考原题
华为机考的介绍点击这里
题目内容
在一个城市的地铁交通网络，有 M 条地铁线路和 N 个地铁站点，每个地铁站都是一个节点，从 0开始按照顺序编号，如果两条不同的地铁线路在同一个地铁站点交汇，表示可以在这个地铁站点从一条地铁线路换乘到另一条线路，即两条线路上出现相同的站点编号意味着是个换乘点，这个地铁站点对于两条地铁线路来说是连通的。现在根据给定需要查询的地铁行程路线（从起始地铁站点到终点地铁站点），请给出这些地铁行程路线的最少地铁线路换乘次数。
输入描述
第一行包含三个整数 n、m 和 k ，分别表示站点数量、地铁线路数量和需要查询的起点站和终点站的组合数量。
接下来 m 行，每行描述一条地铁线路，首先是一个整数 n 表示该线路上的站点数量，然后是 n 个整数，表示线路上的站点编号(从 0 开始)。
接下来 k 行，每行包含两个整数 s 和 t ，表示一次查询的起点站和终点站。n,m,k 取值范围在 [0,1000)
输出描述
对于每次查询，输出一个整数，要示从起点站到终点站的最少换乘次数，如果无法到达，则输出 −1 .
样例1
输入
3 2 2
2 0 1
2 0 2
0 2
0 1
输出
0
0
说明
从站点 0 到站点 2 ，无需换乘直达
从站点 0 到站点 1 ，无需换乘直达
样例2
输入
4 2 2
3 0 1 2
3 1 2 3
0 3
1 3
输出
1
0
说明
从站点 0 到站点 3 ，最少需要换乘 1 次(例如，从 0 到 1 (线路 1 )，然后换乘到线路 2 的 2 站，再到 3 站)；从站点 1 到站点 3 ，不需要换乘(都在线路 2 上)。
