问题描述

我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。例如，有一条路线 routes[0] = [1, 5, 7]，表示第一辆 (下标为 0) 公交车会一直按照 1->5->7->1->5->7->1->... 的车站路线行驶。

假设我们从 S 车站开始（初始时不在公交车上），要去往 T 站。 期间仅可乘坐公交车，求出最少乘坐的公交车数量。返回 -1 表示不可能到达终点车站。

示例：

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

提示：

• 1 <= routes.length <= 500.
• 1 <= routes[i].length <= 10^5.
• 0 <= routes[i][j] < 10 ^ 6.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bus-routes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

• 使用邻接表表示法构造图，关于图和图的邻接表表示法请参考：http://timd.cn/data-structure/graph/

• 使用分支限界算法解题。关于分支限界算法请参考：http://timd.cn/data-structure/branch-and-bound/

• 本题中使用的剪枝函数是：
  当达到某一车站时，首先计算通过乘坐哪些车到达的该车站，以及换乘次数，然后执行下面的流程：

  • 如果之前尚未到达过该站，则将本次到达信息保存到字典中
  • 如果之前曾经到达过该站，那么执行下面的流程：
    • 如果之前到达该站时的换乘次数小于本次到达的换乘次数，则剪去该分支
    • 如果之前到达该站时的换乘次数等于本次到达的换乘次数，则更新到达该站的车辆列表
    • 如果之前到达该站时的换乘次数大于本次到达的换乘次数，则使用本次到达信息更新字典

Python 实现

class Solution(object):
    class Graph(object):
        class HeadNode(object):
            def __init__(self, station_no, next_node=None):
                self.station_no = station_no
                self.next_node = next_node

        class AdjacentNode(object):
            def __init__(self, station_no, next_node=None):
                self.station_no = station_no
                self.next_node = next_node
                self.bus_nos = set()

        def __init__(self):
            self._heads = {}

        def add_edge(self, from_station_no, to_station_no, bus_no=None):
            self._add_edge(from_station_no, to_station_no, bus_no)
            self._add_edge(to_station_no, from_station_no, bus_no)

        def _add_edge(self, from_station_no, to_station_no, bus_no=None):
            if from_station_no not in self._heads:
                self._heads[from_station_no] = self.HeadNode(from_station_no)
            head = self._heads[from_station_no]

            temp = head
            while temp.next_node is not None:
                if temp.next_node.station_no == to_station_no:
                    if bus_no is not None:
                        temp.next_node.bus_nos.add(bus_no)
                    return
                temp = temp.next_node

            if to_station_no not in self._heads:
                self._heads[to_station_no] = self.HeadNode(to_station_no)
            adjacent = self.AdjacentNode(to_station_no)
            if bus_no is not None:
                adjacent.bus_nos.add(bus_no)
            temp.next_node = adjacent

        def get_next_stations(self, station_no):
            if station_no not in self._heads:
                return

            temp = self._heads[station_no]
            while temp.next_node is not None:
                yield temp.next_node
                temp = temp.next_node

        def get_vertex(self, station_no):
            if station_no not in self._heads:
                raise ValueError()
            return self._heads[station_no]

    class Node(object):
        def __init__(self, reach_bus_nos, change_number):
            self.reach_bus_nos = reach_bus_nos
            self.change_number = change_number

    def numBusesToDestination(self, routes, S, T):
        """
        :type routes: List[List[int]]
        :type S: int
        :type T: int
        :rtype: int
        """
        g = self._generate_graph(routes)
        reach_bus_nos = set()
        for n in g.get_next_stations(S):
            reach_bus_nos.update(n.bus_nos)
        if not reach_bus_nos:
            return -1
        if S == T:
            return 0
        stations = {S: self.Node(reach_bus_nos, 1)}
        queue = [S]

        while queue:
            station_no = queue.pop(0)
            for next_station in g.get_next_stations(station_no):
                intersection = stations[station_no].reach_bus_nos & next_station.bus_nos
                arrived_bus_nos = intersection or next_station.bus_nos
                change_number = stations[station_no].change_number + (not intersection)
                if next_station.station_no not in stations or \
                        change_number < stations[next_station.station_no].change_number:
                    stations[next_station.station_no] = self.Node(
                        arrived_bus_nos,
                        change_number)
                    queue.append(next_station.station_no)
                elif change_number == stations[next_station.station_no].change_number:
                    if not arrived_bus_nos.issubset(
                            stations[next_station.station_no].reach_bus_nos):
                        stations[next_station.station_no].reach_bus_nos.update(arrived_bus_nos)
                        queue.append(next_station.station_no)

        if T not in stations:
            return -1
        return stations[T].change_number

    def _generate_graph(self, routes):
        g = self.Graph()
        for bus_no, route in enumerate(routes, start=1):
            for ind in range(len(route) - 1):
                g.add_edge(route[ind], route[ind + 1], bus_no)
        return g