rust 解法, 执行用时: 44 ms, 内存消耗: 13.1 MB, 提交时间: 2024-09-17 22:15:37

use std::collections::{HashMap, VecDeque};

impl Solution {
    pub fn num_buses_to_destination(mut routes: Vec<Vec<i32>>, source: i32, target: i32) -> i32 {
        // 记录经过车站 x 的公交车编号
        let mut stop_to_buses = HashMap::new();
        for (i, route) in routes.iter().enumerate() {
            for &x in route {
                stop_to_buses.entry(x).or_insert(vec![]).push(i);
            }
        }

        // 小优化：如果没有公交车经过起点或终点，直接返回
        if !stop_to_buses.contains_key(&source) || !stop_to_buses.contains_key(&target) {
            // 注意原地 TP 的情况
            return if source != target { -1 } else { 0 };
        }

        // BFS
        let mut dis = HashMap::new();
        dis.insert(source, 0);
        let mut q = VecDeque::new();
        q.push_back(source);
        while let Some(x) = q.pop_front() {
            let dis_x = dis[&x]; // 当前在车站 x
            for &i in &stop_to_buses[&x] { // 遍历所有经过车站 x 的公交车 i
                for &y in &routes[i] { // 遍历公交车 i 的路线
                    if !dis.contains_key(&y) { // 没有访问过车站 y
                        dis.insert(y, dis_x + 1); // 从 x 站上车然后在 y 站下车
                        q.push_back(y);
                    }
                }
                routes[i].clear(); // 标记 routes[i] 遍历过
            }
        }

        dis.get(&target).copied().unwrap_or(-1)
    }
}

python3 解法, 执行用时: 368 ms, 内存消耗: 55.6 MB, 提交时间: 2023-06-13 14:35:57

# 记录每次能坐的所有公交车，将它的所有站都标记为已到达(且加入队列)
class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        # 每个车站可以乘坐的公交车
        stations = defaultdict(set)
        for i, stops in enumerate(routes):
            for stop in stops:
                stations[stop].add(i)
        # 每个公交车线路可以到达的车站
        routes = [set(x) for x in routes]

        q = deque([(source, 0)])
        # 已经乘坐了的公交车
        buses = set()
        # 已经到达了的车站
        stops = {source}
        while q:
            pos, cost = q.popleft()
            if pos == target:
                return cost
            # 当前车站中尚未乘坐的公交车
            for bus in stations[pos] - buses:
                # 该公交车尚未到达过的车站
                for stop in routes[bus] - stops:
                    buses.add(bus)
                    stops.add(stop)
                    q.append((stop, cost + 1))
        return -1

golang 解法, 执行用时: 172 ms, 内存消耗: 23.2 MB, 提交时间: 2023-06-13 14:35:09

func numBusesToDestination(routes [][]int, source, target int) int {
    if source == target {
        return 0
    }

    n := len(routes)
    edge := make([][]bool, n)
    for i := range edge {
        edge[i] = make([]bool, n)
    }
    rec := map[int][]int{}
    for i, route := range routes {
        for _, site := range route {
            for _, j := range rec[site] {
                edge[i][j] = true
                edge[j][i] = true
            }
            rec[site] = append(rec[site], i)
        }
    }

    dis := make([]int, n)
    for i := range dis {
        dis[i] = -1
    }
    q := []int{}
    for _, bus := range rec[source] {
        dis[bus] = 1
        q = append(q, bus)
    }
    for len(q) > 0 {
        x := q[0]
        q = q[1:]
        for y, b := range edge[x] {
            if b && dis[y] == -1 {
                dis[y] = dis[x] + 1
                q = append(q, y)
            }
        }
    }

    ans := math.MaxInt32
    for _, bus := range rec[target] {
        if dis[bus] != -1 && dis[bus] < ans {
            ans = dis[bus]
        }
    }
    if ans < math.MaxInt32 {
        return ans
    }
    return -1
}

javascript 解法, 执行用时: 320 ms, 内存消耗: 91.1 MB, 提交时间: 2023-06-13 14:34:52

/**
 * @param {number[][]} routes
 * @param {number} source
 * @param {number} target
 * @return {number}
 */
var numBusesToDestination = function(routes, source, target) {
    if (source === target) {
        return 0;
    }

    const n = routes.length;
    const edge = new Array(n).fill(0).map(() => new Array(n).fill(0));
    const rec = new Map();
    for (let i = 0; i < n; i++) {
        for (const site of routes[i]) {
            const list = (rec.get(site) || []);
            for (const j of list) {
                edge[i][j] = edge[j][i] = true;
            }
            list.push(i);
            rec.set(site, list);
        }
    }

    const dis = new Array(n).fill(-1);
    const que = [];
    for (const bus of (rec.get(source) || [])) {
        dis[bus] = 1;
        que.push(bus);
    }
    while (que.length) {
        const x = que.shift();
        for (let y = 0; y < n; y++) {
            if (edge[x][y] && dis[y] === -1) {
                dis[y] = dis[x] + 1;
                que.push(y);
            }
        }
    }

    let ret = Number.MAX_VALUE;
    for (const bus of (rec.get(target) || [])) {
        if (dis[bus] !== -1) {
            ret = Math.min(ret, dis[bus]);
        }
    }
    return ret === Number.MAX_VALUE ? -1 : ret;
};

java 解法, 执行用时: 316 ms, 内存消耗: 69.7 MB, 提交时间: 2023-06-13 14:34:39

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }

        int n = routes.length;
        boolean[][] edge = new boolean[n][n];
        Map<Integer, List<Integer>> rec = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < n; i++) {
            for (int site : routes[i]) {
                List<Integer> list = rec.getOrDefault(site, new ArrayList<Integer>());
                for (int j : list) {
                    edge[i][j] = edge[j][i] = true;
                }
                list.add(i);
                rec.put(site, list);
            }
        }

        int[] dis = new int[n];
        Arrays.fill(dis, -1);
        Queue<Integer> que = new LinkedList<Integer>();
        for (int bus : rec.getOrDefault(source, new ArrayList<Integer>())) {
            dis[bus] = 1;
            que.offer(bus);
        }
        while (!que.isEmpty()) {
            int x = que.poll();
            for (int y = 0; y < n; y++) {
                if (edge[x][y] && dis[y] == -1) {
                    dis[y] = dis[x] + 1;
                    que.offer(y);
                }
            }
        }

        int ret = Integer.MAX_VALUE;
        for (int bus : rec.getOrDefault(target, new ArrayList<Integer>())) {
            if (dis[bus] != -1) {
                ret = Math.min(ret, dis[bus]);
            }
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;
    }
}

cpp 解法, 执行用时: 476 ms, 内存消耗: 56.6 MB, 提交时间: 2023-06-13 14:34:23

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) {
            return 0;
        }

        int n = routes.size();
        vector<vector<int>> edge(n, vector<int>(n));
        unordered_map<int, vector<int>> rec;
        for (int i = 0; i < n; i++) {
            for (int site : routes[i]) {
                for (int j : rec[site]) {
                    edge[i][j] = edge[j][i] = true;
                }
                rec[site].push_back(i);
            }
        }

        vector<int> dis(n, -1);
        queue<int> que;
        for (int bus : rec[source]) {
            dis[bus] = 1;
            que.push(bus);
        }
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            for (int y = 0; y < n; y++) {
                if (edge[x][y] && dis[y] == -1) {
                    dis[y] = dis[x] + 1;
                    que.push(y);
                }
            }
        }

        int ret = INT_MAX;
        for (int bus : rec[target]) {
            if (dis[bus] != -1) {
                ret = min(ret, dis[bus]);
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};