头像

MK_4


访客:29

离线:4天前



MK_4
11天前

题目三
【描述】
有n条交通线路,每条线路经过的站点存储在stations[i]中,给定任意两个站点a和b,请输出两站之间换乘次数最少的乘车路线。
输入:stations,a和b
输出:从起点到终点途经的所有站点。

【提示】
1、a 和 b 两个车站一定存在,且不相等。
2、a到b的线路一定存在,但最少换乘线路不一定是唯一的。当存在多种最少换乘线路时,考生只需返回其中之一。
3、每条线路上均存在双向的通车,并且任一条线路中都不会存在环。
4、1<=stations.length<=500, 2<=stations[i].length<=500,
0<=stations[i][j]<=2^31-1

【示例】
示例1:
输入:
stations = [[1, 2, 3, 4], [3, 5, 6, 7]]
a = 1
b = 4
输出: [1,2,3,4]
解释: 只需要坐 0 号线路,就可以从站点 1 到达站点 4。

示例2:
输入:
stations = [[1,2,3,6], [4,5,6,7], [3,5,8,9]]
a = 1
b = 5
输出:[1,2,3,6,5]或[1,2,3,5]
解释: 从a到达b至少有两种换乘方案,方案一:从站点 1 坐 0 号线路,在站点 6 换乘 1 号线路到达站点 5,换乘1次;方案二:从站点 1 坐 0 号线路,在站点 3 换乘 2 号线路到达站点 5,换乘1次。按照题目要求,这两种方法的换乘次数都是最少的,考生可以选择其中之一的路线输出。

【自测案例】
C++/Java/Python的自测输入格式:[[1,2,3,4], [3,5,6,7]];1;4
C语言自测输入格式:[[1,2,3,4], [3,5,6,7]];3;[4,4];1;4
输出:[1,2,3,4]