815. 公交路线

题目描述

输入数组 routes，routes[i] 是第 i 辆公交车经过的车站编号序列。每辆车沿着自己的序列不停循环行驶，例如 [1,5,7] 表示按 1→5→7→1→5→7→… 行驶。

你从车站 source 出发，一开始不在任何车上，目标是到达车站 target。移动只能靠乘坐公交车，可以在两条线路共有的车站换乘。

返回最少需要乘坐多少辆公交车。如果无法到达，返回 -1。若 source 与 target 相同，则不需要乘车。

示例 1

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2

解释：先乘第 0 辆车到车站 7，再换乘第 1 辆车到车站 6，共 2 辆。

示例 2

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

解释：从车站 15 能到达的线路都无法连到车站 12。

数据范围

1 <= routes.length <= 500
1 <= routes[i].length <= 10^5
routes[i] 中的值各不相同。
sum(routes[i].length) <= 10^5
0 <= routes[i][j] < 10^6
0 <= source, target < 10^6

解题思路

代价按“乘坐的公交车数”计算，而不是车站数。先建立“车站 → 经过它的公交车”的索引。以 source 为第 0 层做 BFS，每一层代表多坐一辆车：从当前层的每个车站出发，找到所有还没坐过的公交车，把这些车经过的所有车站一次性加入下一层。每辆公交车只展开一次，第一次碰到 target 时的层数就是答案。

为什么正确

第 rides 层展开的车站，恰好是最少乘坐 rides 辆车才能到达的车站。

复杂度分析

时间 O(Σ|routes[i]|)：每辆车只展开一次，每个车站只入队一次。空间 O(Σ|routes[i]|) 用于索引。

易错点

source == target 时不需要坐车，答案是 0。另外要标记已坐过的公交车，否则一辆很长的线路会被反复展开导致超时。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        stop_to_buses = collections.defaultdict(list)
        for bus, route in enumerate(routes):
            for stop in route:
                stop_to_buses[stop].append(bus)
        used_bus = set()
        seen_stop = {source}
        frontier = [source]
        rides = 0
        while frontier:
            rides += 1
            nxt = []
            for stop in frontier:
                for bus in stop_to_buses[stop]:
                    if bus in used_bus:
                        continue
                    used_bus.add(bus)
                    for s in routes[bus]:
                        if s == target:
                            return rides
                        if s not in seen_stop:
                            seen_stop.add(s)
                            nxt.append(s)
            frontier = nxt
        return -1

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }
        Map<Integer, List<Integer>> stopToBuses = new HashMap<>();
        for (int bus = 0; bus < routes.length; bus++) {
            for (int stop : routes[bus]) {
                stopToBuses.computeIfAbsent(stop, k -> new ArrayList<>()).add(bus);
            }
        }
        Set<Integer> usedBus = new HashSet<>();
        Set<Integer> seenStop = new HashSet<>();
        seenStop.add(source);
        List<Integer> frontier = new ArrayList<>();
        frontier.add(source);
        int rides = 0;
        while (!frontier.isEmpty()) {
            rides++;
            List<Integer> nxt = new ArrayList<>();
            for (int stop : frontier) {
                for (int bus : stopToBuses.getOrDefault(stop, new ArrayList<>())) {
                    if (usedBus.contains(bus)) {
                        continue;
                    }
                    usedBus.add(bus);
                    for (int s : routes[bus]) {
                        if (s == target) {
                            return rides;
                        }
                        if (!seenStop.contains(s)) {
                            seenStop.add(s);
                            nxt.add(s);
                        }
                    }
                }
            }
            frontier = nxt;
        }
        return -1;
    }
}

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) {
            return 0;
        }
        unordered_map<int, vector<int>> stopToBuses;
        for (int bus = 0; bus < (int)routes.size(); bus++) {
            for (int stop : routes[bus]) {
                stopToBuses[stop].push_back(bus);
            }
        }
        unordered_set<int> usedBus;
        unordered_set<int> seenStop = {source};
        vector<int> frontier = {source};
        int rides = 0;
        while (!frontier.empty()) {
            rides++;
            vector<int> nxt;
            for (int stop : frontier) {
                for (int bus : stopToBuses[stop]) {
                    if (usedBus.count(bus)) {
                        continue;
                    }
                    usedBus.insert(bus);
                    for (int s : routes[bus]) {
                        if (s == target) {
                            return rides;
                        }
                        if (!seenStop.count(s)) {
                            seenStop.insert(s);
                            nxt.push_back(s);
                        }
                    }
                }
            }
            frontier = nxt;
        }
        return -1;
    }
};

func numBusesToDestination(routes [][]int, source int, target int) int {
	if source == target {
		return 0
	}
	stopToBuses := map[int][]int{}
	for bus, route := range routes {
		for _, stop := range route {
			stopToBuses[stop] = append(stopToBuses[stop], bus)
		}
	}
	usedBus := map[int]bool{}
	seenStop := map[int]bool{source: true}
	frontier := []int{source}
	rides := 0
	for len(frontier) > 0 {
		rides++
		nxt := []int{}
		for _, stop := range frontier {
			for _, bus := range stopToBuses[stop] {
				if usedBus[bus] {
					continue
				}
				usedBus[bus] = true
				for _, s := range routes[bus] {
					if s == target {
						return rides
					}
					if !seenStop[s] {
						seenStop[s] = true
						nxt = append(nxt, s)
					}
				}
			}
		}
		frontier = nxt
	}
	return -1
}

var numBusesToDestination = function(routes, source, target) {
    if (source === target) {
        return 0;
    }
    const stopToBuses = new Map();
    routes.forEach((route, bus) => {
        for (const stop of route) {
            if (!stopToBuses.has(stop)) stopToBuses.set(stop, []);
            stopToBuses.get(stop).push(bus);
        }
    });
    const usedBus = new Set();
    const seenStop = new Set([source]);
    let frontier = [source];
    let rides = 0;
    while (frontier.length > 0) {
        rides++;
        const nxt = [];
        for (const stop of frontier) {
            for (const bus of stopToBuses.get(stop) || []) {
                if (usedBus.has(bus)) {
                    continue;
                }
                usedBus.add(bus);
                for (const s of routes[bus]) {
                    if (s === target) {
                        return rides;
                    }
                    if (!seenStop.has(s)) {
                        seenStop.add(s);
                        nxt.push(s);
                    }
                }
            }
        }
        frontier = nxt;
    }
    return -1;
};

function numBusesToDestination(routes: number[][], source: number, target: number): number {
    if (source === target) {
        return 0;
    }
    const stopToBuses = new Map<number, number[]>();
    routes.forEach((route, bus) => {
        for (const stop of route) {
            if (!stopToBuses.has(stop)) stopToBuses.set(stop, []);
            stopToBuses.get(stop)!.push(bus);
        }
    });
    const usedBus = new Set();
    const seenStop = new Set([source]);
    let frontier = [source];
    let rides = 0;
    while (frontier.length > 0) {
        rides++;
        const nxt: number[] = [];
        for (const stop of frontier) {
            for (const bus of stopToBuses.get(stop) || []) {
                if (usedBus.has(bus)) {
                    continue;
                }
                usedBus.add(bus);
                for (const s of routes[bus]) {
                    if (s === target) {
                        return rides;
                    }
                    if (!seenStop.has(s)) {
                        seenStop.add(s);
                        nxt.push(s);
                    }
                }
            }
        }
        frontier = nxt;
    }
    return -1;
}

载入编辑器，自己跑一遍 →

图论专题的其他题目

查看图论全部题目 →