公交路线

记住「建站→线路映射、再以线路为节点 BFS,层数就是乘车数」,下面逐帧套它。

先把 3 条线路各画成一个节点:R0=[1,2,7]、R1=[3,6,7]、R2=[6,8,9],此刻还没有任何边。下面逐站扫描,谁和谁共享站点,就在谁和谁之间连一条「可换乘」的边。

处理 R0 的站 1:把 R0 记到「站 1」名下。目前只有它一条线路经过这站,先记着。

处理 R0 的站 2:把 R0 记到「站 2」名下。目前只有它一条线路经过这站,先记着。

处理 R0 的站 7:把 R0 记到「站 7」名下。目前只有它一条线路经过这站,先记着。

处理 R1 的站 3:把 R1 记到「站 3」名下。目前只有它一条线路经过这站,先记着。

处理 R1 的站 6:把 R1 记到「站 6」名下。目前只有它一条线路经过这站,先记着。

线路 R1 经过站 7,而站 7 之前已经被 R0 记下了。这说明在站 7 可以从 R0 换乘到 R1,于是给 R0 和 R1 连一条边(高亮)。

线路 R2 经过站 6,而站 6 之前已经被 R1 记下了。这说明在站 6 可以从 R1 换乘到 R2,于是给 R1 和 R2 连一条边(高亮)。

处理 R2 的站 8:把 R2 记到「站 8」名下。目前只有它一条线路经过这站,先记着。

处理 R2 的站 9:把 R2 记到「站 9」名下。目前只有它一条线路经过这站,先记着。

映射建好了:站 7 把 R0、R1 连起来,站 6 把 R1、R2 连起来。现在这张「线路图」就成形了,接下来在它上面做 BFS,数从起点线路到含 target 的线路要走几步。

起点是站 1。先查映射:经过站 1 的线路是 R0,把它们入队、标记为已坐(乘车数从 1 起步)。BFS 第一层就是「坐第 1 辆车能到的线路」。

弹出队首 R0(紫色),它是坐第 1 辆车能到的线路之一。先看终点站 9 在不在它停靠的站里。

终点站 9 不在 R0 里。通过共享站换乘到新线路 R1(站 7),把它们入队、标记已坐。 R0 这条线路本轮处理完(变绿)。

第 1 辆车能到的线路都查完了,还没碰到终点。乘车数加到 2,继续处理队列里下一层的线路。

弹出队首 R1(紫色),它是坐第 2 辆车能到的线路之一。先看终点站 9 在不在它停靠的站里。

终点站 9 不在 R1 里。通过共享站换乘到新线路 R2(站 6),把它们入队、标记已坐。 R1 这条线路本轮处理完(变绿)。

第 2 辆车能到的线路都查完了,还没碰到终点。乘车数加到 3,继续处理队列里下一层的线路。

弹出队首 R2(紫色),它是坐第 3 辆车能到的线路之一。先看终点站 9 在不在它停靠的站里。

R2 停靠的站 [6,8,9] 里有终点站 9(变绿)!说明坐到第 3 辆车就能抵达,答案就是 3。BFS 第一次碰到含 target 的线路,层数即最少乘车数。

边界:同站 0、不可达 −1、同线 1。

两个追问:线路为节点免去 0-1 边;预建映射让换乘查询线性。