0815. Bus Routes

题目信息

题号:

0815

难度:

Hard

主题:

公交线路、换乘、最少乘车数

原题:

LeetCode 0815

重点:

每条线路会循环经过其全部站点;答案统计乘坐过的公交线路数量,而不是站点数或行驶段数

题目重述

给定公交线路数组 routes,其中 routes[i] 列出第 i 辆公交车循环经过的所有站点。登上一辆公交后,可以到达该线路中的任意站点;在两个线路共有的站点可以换乘另一辆公交。

给定起点站 source 和目标站 target,请返回从起点到目标至少需要乘坐多少辆公交车。若 source == target,无需乘车,返回 0;若无法到达目标,返回 -1。

1 <= routes.length <= 500,每条线路包含至少一个站点,所有线路的站点数总和不超过 10^5;同一线路内站点互不重复,站点编号、source 和 target 均在 [0, 10^6] 范围内。

自建示例

需要连续换乘两次:

输入:routes = [[1,4,7],[3,6,7],[6,9]], source = 1, target = 9
输出:3
解释:先乘第一条线路从 1 到 7,换乘第二条到 6,再换乘第三条到 9,共乘坐三辆公交。

起点就是目标:

输入:routes = [[2,5,8]], source = 5, target = 5
输出:0
解释:已经位于目标站,不需要乘坐公交。