#include<bits/stdc++.h>
using namespace std;
vector<int>LuXian[550];
map<int,vector<int>>ZhanDian;
map<int,int>dis;
void Bfs(int B){
	set<int>bookLX;
	set<int>bookZD;
	queue<int>que;
	que.push(B);
	bookZD.insert(B);
	dis[B]=0;
	while(!que.empty()){
		int x=que.front(); que.pop();
		for(auto id:ZhanDian[x]){
			if(bookLX.find(id)==bookLX.end()){
				bookLX.insert(id);
				for(auto y:LuXian[id]){
					if(bookZD.find(y)!=bookZD.end())continue;
					bookZD.insert(y);
					dis[y]=dis[x]+1;
					que.push(y);
				}
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int A,B,C; cin>>A>>B>>C;
	int N; cin>>N;
	for(int i=1;i<=N;i++){
		int n; cin>>n;
		for(int j=1;j<=n;j++){
			int x; cin>>x;
			LuXian[i].push_back(x);
			ZhanDian[x].push_back(i);
		}
	}
	Bfs(B);
	if(dis.find(A)==dis.end()||dis.find(C)==dis.end())cout<<-1;
	else cout<<dis[A]+dis[C]-1;
	return 0;
}

类似题目推荐

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);
        }

    }


}