类似题目推荐

LeetCode 815. 公交路线

题面解释

题目描述了小塔作为一名环保爱好者，如何选择公交车上班的最佳路线。给定小塔的上车站台、购买早餐的站台以及下车站台的编号，接着提供公交路线的信息，包括每条公交路线经过的站台编号。任务是帮助小塔选择乘坐公交车的总数最少的路线，如果无法找到合适的公交路线，则返回-1。输入包括三行，第一行是上车、早餐店和下车的站台编号，第二行是公交路线的数量，后续每行提供一条公交路线的信息。输出为小塔所需乘坐的公交车总数。

关键

题目内容

小明是一名环保爱好者，每天选择乘坐公交车上班。不同线路上的公交车会在规定的路线上单向循环行驶，例如$708$路公交的路线为[$2,5,8$]，那么公交车会按照$2->5->8->2->5->8->...$.的路线循环行驶，其中路线中的数字为公交站台编号。

小明每天上班会从离他家里最近的公交站台上车，然后在他最喜欢的早餐店所在的站台下车买好早餐然后再上车，最后在离公司最近的公交站台下车，允许不限次数地在中途下车换乘其他路线的公交。

现在分别给定小明上车、早餐店、下车的公交站台编号，请帮他选择最佳的乘车路线，使乘坐的公交车总数最少(如果在同$1$条公交路线中下车再上车，仍然视为乘坐的同一辆车)，从而获得最好的通勤体验。

输入描述

$1$.第一行有$3$个数字，分别表示上车的公交站台编号、早餐店的公交站台编号、下车公交站台编号，依次用空格隔开。

$2$.第二行表示公交路线数量，后续的每一行中第$1$个数字代表该路线的总站台数，剩余的数字表示每条公交路线经过的站点编号，所有数字用空格隔开。

$3$.公交路线数量范围在[$1,500$]。

$4$.公交站台的编号范围在[$1,1000000$]。

$5$.每条公交路线经过的站台数量范围在[$2,1500$]，路线中的站台编号按升序顺序排序，且每条路线中不包含重复的站台。

$6$.起点站台、购买早餐的站点、终点站台不重复。

输出描述

乘坐的公交路线总数，如果没有匹配的路线请返回$-1$

样例1

输入

1 3 5
4
3 1 2 6
3 2 3 7
3 5 6 8
2 5 7

输出

3

说明

先乘坐第$1$条公交路线的车，在第$2$个站点下车转第$2$条路线的公交车，然后再乘坐第$2$条公交路线的车在站点$3$下车买早餐，然后重新乘坐第$2$条公交路线达到站点$7$下车转第$4$条公交路线，最后达到站点$5$，经过的公交路线为$1->2->4$，所以结果为$3$。虽然乘坐第$1$条公交路线和第$3$条公交路线也能达到站点$5$，但是该路线没法购买早餐。

样例2

输入

1 3 4
2 
3 1 2 4
3 3 5 6

输出

-1

说明

小王只能乘坐第$1$条公交路线上车，但是无法通过该路线的站台换乘到第$2$条公交路线购买早餐，没有匹配的路线，返回$-1$。

样例3

输入

4 19 28
5
5 3 4 7 8 10
6 10 12 16 19 27 28
4 5 7 11 17
4 17 19 22 23
3 23 27 28

输出

2

说明

小王可以选择$1->2$的公交路线，乘坐的公交车总数为$2$，也可以选择$1->3->4->5$的公交路线，乘坐的公交车总数为$4$，因此最佳的乘车路线是$1->2$，结果为$2$。