0815. Bus Routes¶
题目信息¶
- 题号:
0815
- 难度:
Hard
- 主题:
公交线路、换乘、最少乘车数
- 原题:
- 重点:
每条线路会循环经过其全部站点;答案统计乘坐过的公交线路数量,而不是站点数或行驶段数
题目重述¶
给定公交线路数组 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
解释:已经位于目标站,不需要乘坐公交。