类似题目推荐

LeetCode 815. 公交路线

题面解释

题目描述了小塔作为一名环保爱好者，如何选择公交车上班的最佳路线。给定小塔的上车站台、购买早餐的站台以及下车站台的编号，接着提供公交路线的信息，包括每条公交路线经过的站台编号。任务是帮助小塔选择乘坐公交车的总数最少的路线，如果无法找到合适的公交路线，则返回-1。输入包括三行，第一行是上车、早餐店和下车的站台编号，第二行是公交路线的数量，后续每行提供一条公交路线的信息。输出为小塔所需乘坐的公交车总数。

关键

1.每个公交线路最多访问一次&题目要求的是线路换乘次数，而不是坐的站点的次数 <=>对公交线路进行bfs <=> dist[i]代表从某起点到第i个公交线路的最短路径

2.无向图里上->早餐->下 等价 早餐->上 + 早餐 + 下

3.计算任意两个站点x,y之间的最短最少换乘 dist(x,y):

从所有拥有x的公交线路出发,多源bfs,计算到达拥有y的站点的任意公交线路的最小值

做法:

利用3计算 dist(早,上) + dist(早,下)

题解

本题要求我们帮助小塔选择最佳的公交车路线，以最小化乘坐公交车的次数，具体步骤如下：

1. 问题分析

小塔需要完成三段旅程：从起点公交站到早餐店，再从早餐店到终点公交站。由于允许在任意公交站换乘，实际问题可以转化为计算从起点到早餐店和从早餐店到终点的最短换乘次数。

2. 输入输出格式

• 输入：第一行包含三个整数，分别是起点公交站台编号、早餐店公交站台编号和终点公交站台编号。第二行是公交路线的数量，后续每行描述每条公交路线的站点编号。
• 输出：如果存在合适的公交路线，输出最小的乘坐公交车次数；否则输出 -1。

3. 数据结构

• 使用vector<vector<int>> bus_routes来存储每条公交线路的站点。
• 使用unordered_map<int, vector<int>> bus_trans来记录每个站点所经过的公交路线，方便后续查找。

4. 算法实现

为了计算两站点之间的最短换乘次数，我们使用广度优先搜索（BFS）进行多源搜索：

• BFS函数：从某一条公交线路出发，遍历所有经过的站点，获取到其他公交线路的最短距离。
• 换乘次数计算：
  1. 从早餐店出发，计算能够到达的公交线路。
  2. 遍历所有从起点和终点出发的公交线路，计算最小换乘次数。
  3. 将起点到早餐店的换乘次数与早餐店到终点的换乘次数相加，得到总的换乘次数。

5. 特殊情况处理

如果在计算过程中发现无法从起点或终点到达早餐店，则需返回 -1。

代码如下

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 定义一个函数来进行广度优先搜索
vector<int> bfs(const vector<vector<int>>& bus_routes, const unordered_map<int, vector<int>>& bus_trans, const vector<int>& start_routes) {
    int n = bus_routes.size();
    vector<int> dist(n, -1);  // 距离数组，初始值为-1，表示未访问的公交线路
    queue<int> q;  // 用于广度优先搜索的队列

    // 将起始公交线路编号加入队列并设置其距离为0
    for (int id : start_routes) {
        q.push(id);
        dist[id] = 0;
    }

    // 开始广度优先搜索
    while (!q.empty()) {
        int cur = q.front(); q.pop();  // 取出队列最前面的公交线路

        // 枚举该公交线路的所有站点
        for (int port : bus_routes[cur]) {
            // 查看每个站点所经过的其他公交线路
            for (int bus_id : bus_trans.at(port)) {
                // 如果该公交线路没有被访问过
                if (dist[bus_id] == -1) {
                    // 记录该公交线路的距离为当前距离 + 1
                    dist[bus_id] = dist[cur] + 1;
                    q.push(bus_id);  // 将该公交线路加入队列
                }
            }
        }
    }

    return dist;
}

int main() {
    // 输入起点、早餐店、终点的站点 id
    int start_id, mid_id, end_id;
    cin >> start_id >> mid_id >> end_id;

    // 输入公交线路数量
    int n;
    cin >> n;

    // 初始化公交路线，每个公交线路对应一条列表，记录站点
    vector<vector<int>> bus_routes(n);
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;  // 读取站点数量
        bus_routes[i].resize(m);
        for (int j = 0; j < m; j++) {
            cin >> bus_routes[i][j];  // 读取每个站点
        }
    }

    // 创建一个哈希表，记录每个站点所经过的公交路线
    unordered_map<int, vector<int>> bus_trans;
    for (int i = 0; i < n; i++) {
        for (int x : bus_routes[i]) {
            bus_trans[x].push_back(i);  // 将公交路线编号添加到该站点的依赖中
        }
    }

    long long ans = 10e15;  // 初始化答案为一个大的值

    // 从早餐店出发，计算到各个公交线路的最短距离
    for (int bus_id : bus_trans[mid_id]) {
        vector<int> dist = bfs(bus_routes, bus_trans, {bus_id});  // BFS 搜索从早餐店出发的最短路径

        // 计算从起点到早餐店的最短路径
        long long min_dist_to_start = 10e15;  // 初始化距离为很大的值
        for (int bus_id : bus_trans[start_id]) {
            // 如果存在从起点的站点所在公交线路到达早餐店的路径
            if (dist[bus_id] != -1) {
                min_dist_to_start = min(min_dist_to_start, (long long)dist[bus_id]);
            }
        }

        // 计算从终点到早餐店的最短路径
        long long min_dist_to_end = 10e15;  // 初始化距离为很大的值
        for (int bus_id : bus_trans[end_id]) {
            // 如果存在从终点的站点所在公交线路到达早餐店的路径
            if (dist[bus_id] != -1) {
                min_dist_to_end = min(min_dist_to_end, (long long)dist[bus_id]);
            }
        }

        // 如果起点或终点无法到达早餐店，输出-1
        if (min_dist_to_start == 10e15 || min_dist_to_end == 10e15) {
            continue;
        } else {
            ans = min(ans, min_dist_to_start + min_dist_to_end + 1);  // 更新答案
        }
    }

    // 输出最终答案
    if (ans == 10e15) {
        cout << -1 << endl;  // 如果没有找到合适的路径
    } else {
        cout << ans << endl;  // 输出最短路径
    }

    return 0;
}

Python

from collections import defaultdict

# 输入起点、早餐店、终点的站点id
start_id, mid_id, end_id = map(int, input().split())

# 输入公交线路数量
n = int(input())

# 初始化公交路线，每个公交线路对应一条列表，记录站点
bus_routes = [[] for _ in range(n)]
for i in range(n):
    # 读取每条公交线路的站点，并忽略第一项（该项为站点数量）
    bus_routes[i] = list(map(int, input().split()))[1:]

# 创建一个字典，记录每个站点所经过的公交路线，字典值为公交路线编号列表
bus_trans = defaultdict(list)
for i in range(n):
    for x in bus_routes[i]:
        bus_trans[x].append(i)

# 定义广度优先搜索函数，计算从指定的公交线路出发到达其他公交线路的最短距离
def bfs(start_routes):
    q = []  # 用于广度优先搜索的队列
    dist = [-1 for _ in range(n)]  # 距离数组，初始值为-1，表示未访问的公交线路
    # 将起始公交线路编号加入队列并设置其距离为0
    for id in start_routes:
        q.append(id)
        dist[id] = 0
    # 开始广度优先搜索
    while q:
        cur = q.pop(0)  # 取出队列最前面的公交线路
        # 枚举该公交线路的所有站点
        for port in bus_routes[cur]:
            # 查看每个站点所经过的其他公交线路
            for bus_id in bus_trans[port]:
                # 如果该公交线路没有被访问过
                if dist[bus_id] == -1:
                    # 记录该公交线路的距离为当前距离+1
                    dist[bus_id] = dist[cur] + 1
                    q.append(bus_id)  # 将该公交线路加入队列
    return dist

ans = 10**15
# 从早餐店出发，计算到各个公交线路的最短距离
for bus_id in bus_trans[mid_id]:
    dist = bfs([bus_id])
    # 计算从起点到早餐店的最短路径
    min_dist_to_start = 10**15  # 初始化距离为很大的值
    for bus_id in bus_trans[start_id]:
        # 如果存在从起点的站点所在公交线路到达早餐店的路径
        if dist[bus_id] != -1:
            min_dist_to_start = min(min_dist_to_start, dist[bus_id])

    # 计算从终点到早餐店的最短路径
    min_dist_to_end = 10**15  # 初始化距离为很大的值
    for bus_id in bus_trans[end_id]:
        # 如果存在从终点的站点所在公交线路到达早餐店的路径
        if dist[bus_id] != -1:
            min_dist_to_end = min(min_dist_to_end, dist[bus_id])
    # 如果起点或终点无法到达早餐店，输出-1
    if min_dist_to_start == 10**15 or min_dist_to_end == 10**15:
        continue 
    else:
        ans = min(ans , min_dist_to_start + min_dist_to_end + 1)

if ans == 10**15:
    print(-1)
else:
    print(ans)

Java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int upNo = in.nextInt(), midNo = in.nextInt(), downNo= in.nextInt( );
        List<List<Integer>> busList = new ArrayList<>();
        busList.add(null);
        Map<Integer, List<Integer>> routeList = new HashMap<>();
        int busNo = in.nextInt();
        in.nextLine();
        for (int i = 1;i <= busNo;i++){
            int stopNo = in.nextInt();
            List<Integer> list = new ArrayList<>();
            for (int j = 0;j < stopNo;j++) {
                int stop = in.nextInt();
                list.add(stop);
                List<Integer> route = routeList.get(stop);
                if (route == null) {
                    route = new ArrayList<>();
                }
                route.add(i);
                routeList.put(stop, route);
            }
            busList.add(list);
        }

        boolean[] vis = new boolean[busNo+1];
        Deque<Integer> queue = new ArrayDeque<>();
        //将所有早餐店站点的公交车加入队列，注意该站点可能没有公交车
        List<Integer> midRoute = routeList.get(midNo);
        if (midRoute != null) {
            queue.addAll(midRoute);
        } else {
            System.out.println(-1);
            return;
        }
        int dist = 1, upDist=Integer.MAX_VALUE, downDist= Integer.MAX_VALUE;
        while(!queue.isEmpty()){
            //每次将队列中的所有公交车出队，然后将这些公交车可以到达的站点的公交车加入队列
            //在访问公交车可以到达的站点时，如果找到上车点和下车点，直接返回
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int bus = queue.poll();
                for (int stop : busList.get(bus)) {
                    if (stop == upNo) {
                        upDist = Math.min(upDist,dist);
                        if (downDist != Integer.MAX_VALUE) {
                            System.out.println(upDist + downDist - 1);
                            return;
                        }
                    }
                    if (stop == downNo) {
                        downDist = Math.min(downDist,dist);
                        if (upDist != Integer.MAX_VALUE) {
                            System.out.println(upDist + downDist - 1);
                            return;
                        }
                    }
                    for (int nextBus : routeList.get(stop)) {
                        if (!vis[nextBus]) {
                            vis[nextBus] = true;
                            queue.add(nextBus);
                        }
                    }
                }
            }
            dist++;
        }
        if (upDist == Integer.MAX_VALUE || downDist == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(upDist + downDist - 1);
        }

    }


}

题目内容

小明是一名环保爱好者，每天选择乘坐公交车上班。不同线路上的公交车会在规定的路线上单向循环行驶，例如$708$路公交的路线为[$2,5,8$]，那么公交车会按照$2->5->8->2->5->8->...$.的路线循环行驶，其中路线中的数字为公交站台编号。

小明每天上班会从离他家里最近的公交站台上车，然后在他最喜欢的早餐店所在的站台下车买好早餐然后再上车，最后在离公司最近的公交站台下车，允许不限次数地在中途下车换乘其他路线的公交。

现在分别给定小明上车、早餐店、下车的公交站台编号，请帮他选择最佳的乘车路线，使乘坐的公交车总数最少(如果在同$1$条公交路线中下车再上车，仍然视为乘坐的同一辆车)，从而获得最好的通勤体验。

输入描述

$1$.第一行有$3$个数字，分别表示上车的公交站台编号、早餐店的公交站台编号、下车公交站台编号，依次用空格隔开。

$2$.第二行表示公交路线数量，后续的每一行中第$1$个数字代表该路线的总站台数，剩余的数字表示每条公交路线经过的站点编号，所有数字用空格隔开。

$3$.公交路线数量范围在[$1,500$]。

$4$.公交站台的编号范围在[$1,1000000$]。

$5$.每条公交路线经过的站台数量范围在[$2,1500$]，路线中的站台编号按升序顺序排序，且每条路线中不包含重复的站台。

$6$.起点站台、购买早餐的站点、终点站台不重复。

输出描述

乘坐的公交路线总数，如果没有匹配的路线请返回$-1$

样例1

输入

1 3 5
4
3 1 2 6
3 2 3 7
3 5 6 8
2 5 7

输出

3

说明

先乘坐第$1$条公交路线的车，在第$2$个站点下车转第$2$条路线的公交车，然后再乘坐第$2$条公交路线的车在站点$3$下车买早餐，然后重新乘坐第$2$条公交路线达到站点$7$下车转第$4$条公交路线，最后达到站点$5$，经过的公交路线为$1->2->4$，所以结果为$3$。虽然乘坐第$1$条公交路线和第$3$条公交路线也能达到站点$5$，但是该路线没法购买早餐。

样例2

输入

1 3 4
2
3 1 2 4
3 3 5 6

输出

-1

说明

小王只能乘坐第$1$条公交路线上车，但是无法通过该路线的站台换乘到第$2$条公交路线购买早餐，没有匹配的路线，返回$-1$。

样例3

输入

4 19 28
5
5 3 4 7 8 10
6 10 12 16 19 27 28
4 5 7 11 17
4 17 19 22 23
3 23 27 28

输出

2

说明

小王可以选择$1->2$的公交路线，乘坐的公交车总数为$2$，也可以选择$1->3->4->5$的公交路线，乘坐的公交车总数为$4$，因此最佳的乘车路线是$1->2$，结果为$2$。