公交路线

06/28/2021

题目描述

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。期间仅可乘坐公交车。

求出最少乘坐的公交车数量。如果不可能到达终点车站，返回 -1 。

示例 1：

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：

输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1

提示：

1 <= routes.length <= 500
1 <= routes[i].length <= 10⁵
routes[i] 中的所有值互不相同
sum(routes[i].length) <= 10⁵
0 <= routes[i][j] < 10⁶
0 <= source, target < 10⁶

本人题解

/**
 * @param {number[][]} routes
 * @param {number} source
 * @param {number} target
 * @return {number}
 */
var numBusesToDestination = function(routes, source, target) {
    if (source == target) {
        return 0
    }
    let stations = {};    
    routes.forEach((r, i) => {
        r.forEach(s => {
            if (stations[s]) {
                stations[s].push(i)
            } else {
                stations[s] = [i]
            }
        })
    })
    let paths = [[]], result = -1, passed = {[source]: true};
    while (paths.length > 0 && result == -1) {
        let ps = [...paths]
        paths = []
        ps.forEach(p => go(p))
    }
    function addToPath(path, s) {
        if (!passed[s]) {
            passed[s] = true
            let newP = [...path, s]
            paths.push(newP)
            if (s == target) {
                result = newP.length
            }
        }
    }
    function go(path) {
        if (result != -1) {
            return
        }
        let start = path[path.length-1] || source
        let stops = stations[start].flatMap(s => routes[s] || [])
        stops.forEach(s => {
            addToPath(path, s)
        })
        rmLines(start)
        rmStations(start)
    }
    function rmLines(s) {
        stations[s].forEach(sta => {
            routes[sta] = []
        })
    }
    function rmStations(s) {
        stations[s] = []
    }
    return result
};

分析

忘了。以后再补