题面描述

在这道题中，我们需要帮助塔子规划从起点星球到终点星球的最短路径，给定的路径由若干通行证定义。输入包括通行证的数量和起点、终点的编号，以及每个通行证的起止星球。输出应为塔子需要经过的星球数量（不包括起点），若无法到达终点，则返回 -1。我们可以使用广度优先搜索（BFS）算法来解决此问题，通过构建星球间的图结构，逐层探索可达星球，以找到最短路径或判断不可达。

思路: bfs

朴素的bfs求最短路的题

算法步骤：

1. 图的表示：使用邻接表来表示图。对于每个通行证（边），将起点和终点加入到相应的列表中。
2. 初始化：创建一个数组 vis 用于标记每个星球是否被访问过，以及记录到达该星球所需的步数。
3. BFS搜索：
   • 初始化队列，将起点放入队列。
   • 进行循环，直到队列为空。在每一层中，遍历当前层的所有星球，并对每个星球的相邻星球进行处理。
   • 如果相邻星球尚未被访问，则更新其访问步数，并将其加入队列。
   • 步数在每一层结束时自增，确保每次都能正确计算到达每个星球的最小步数。
4. 结果输出：检查终点星球的访问步数，如果仍为 0，则表示不可达，输出 -1；否则输出访问步数。

代码

C++

#include<bits/stdc++.h>
using namespace std;

// 定义邻接表
vector<vector<int>> edge;
int vis[100010]; // 访问数组，用于记录每个星球的访问状态和步数
int m1, m2; // 起点和终点星球编号

int main()
{
    edge.resize(100010); // 初始化邻接表
    int n;
    cin >> n >> m1 >> m2; // 输入通行证数量和起终点编号
    
    // 读取通行证信息，构建图
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y; // 输入每个通行证的起点和终点
        edge[x].push_back(y); // 建立有向边
    }

    int step = 0; // 步数计数器
    queue<int> qu; // 队列用于 BFS
    qu.push(m1); // 将起点加入队列
    
    while (!qu.empty()) // 当队列不为空时继续进行 BFS
    {
        int sz = qu.size(); // 当前层的节点数量
        for (int i = 0; i < sz; i++)
        {
            int top = qu.front(); // 获取队列头部元素
            qu.pop(); // 弹出队列头部元素
            for (int v : edge[top]) // 遍历当前节点的所有邻接节点
            {
                if (vis[v]) // 如果邻接节点已经被访问过
                    continue; // 跳过该节点
                vis[v] = step + 1; // 更新访问步数
                qu.push(v); // 将邻接节点加入队列
            }
        }
        // 步数自增，准备处理下一层节点
        step++;
    }
    
    // 判断终点是否被访问过
    if (vis[m2] == 0)
        cout << -1 << endl; // 如果没有访问到终点，输出 -1
    else
        cout << vis[m2] << endl; // 否则输出到达终点的步数
    
    return 0; // 程序结束
}

Python

import sys
from collections import deque, defaultdict

# 广度优先搜索函数，返回从起点到终点的最短路径长度
def bfs(graph, start, end):
    # 如果起点和终点相同，直接返回 0
    if start == end:
        return 0
    
    # 初始化队列，存储当前节点和到达该节点的距离
    queue = deque([(start, 0)])
    # 使用集合来记录已访问的节点
    visited = set([start])
    
    # 开始 BFS 循环
    while queue:
        current, distance = queue.popleft()  # 弹出队列的第一个元素
        
        # 遍历当前节点的所有邻居
        for neighbor in graph[current]:
            if neighbor not in visited:  # 如果邻居节点尚未被访问
                if neighbor == end:  # 如果找到终点
                    return distance + 1  # 返回当前距离加一
                visited.add(neighbor)  # 标记邻居为已访问
                queue.append((neighbor, distance + 1))  # 将邻居加入队列，距离加一
    
    return -1  # 如果队列遍历完仍未找到终点，返回 -1

# 主函数
def main():
    input = sys.stdin.read  # 从标准输入读取所有数据
    data = input().split()  # 将输入数据按空格分割为列表
    index = 0
    
    # 读取通行证数量、起点和终点
    n = int(data[index])  # 通行证数量
    index += 1
    m1 = int(data[index])  # 起点编号
    index += 1
    m2 = int(data[index])  # 终点编号
    index += 1
    
    # 初始化图的邻接表
    graph = defaultdict(list)
    for _ in range(n):
        u = int(data[index])  # 读取边的起点
        index += 1
        v = int(data[index])  # 读取边的终点
        index += 1
        graph[u].append(v)  # 将边添加到图中
    
    # 调用 BFS 函数计算从 m1 到 m2 的最短路径
    result = bfs(graph, m1, m2)
    print(result)  # 输出结果

# 程序入口
if __name__ == "__main__":
    main()  # 执行主函数

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建输入扫描器

        // 读取输入的通行证数量、起点和终点
        int n = sc.nextInt(); // 通行证数量
        int start = sc.nextInt(); // 起点编号
        int end = sc.nextInt(); // 终点编号

        // 使用哈希表来存储图的邻接表，键是起点，值是与之相连的终点集合
        Map<Integer, Set<Integer>> map = new HashMap<>();

        // 读取每个通行证的信息，构建图
        for (int i = 0; i < n; i++) {
            int from = sc.nextInt(); // 通行证的起点
            int to = sc.nextInt(); // 通行证的终点

            // 获取起点对应的终点集合，如果不存在则创建一个新的集合
            Set<Integer> set = map.getOrDefault(from, new HashSet<>());
            set.add(to); // 将终点添加到集合中
            map.put(from, set); // 更新哈希表
        }

        // 如果起点在图中不存在，直接输出 -1
        if(!map.containsKey(start)){
            System.out.println(-1);
            return;
        }

        // 初始化队列用于广度优先搜索
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start); // 将起点加入队列

        int cnt = 0; // 步数计数器
        Set<Integer> set = new HashSet<>(); // 记录已访问的节点
        set.add(start); // 将起点标记为已访问

        // 开始广度优先搜索
        while (!queue.isEmpty()){
            int size = queue.size(); // 当前层节点数量
            for (int i = 0; i < size; i++) {
                int from = queue.poll(); // 从队列中取出一个节点
                // 检查是否到达终点
                if(from == end){
                    System.out.println(cnt); // 输出当前步数
                    return;
                }
                // 如果当前节点在图中有邻接节点
                if(map.containsKey(from)){
                    for(int to : map.get(from)){ // 遍历所有邻接节点
                        // 如果邻接节点尚未被访问
                        if(!set.contains(to)){
                            set.add(to); // 标记为已访问
                            queue.add(to); // 将其加入队列
                        }
                    }
                }
            }
            cnt++; // 步数自增，进入下一层搜索
        }
        System.out.println(-1); // 如果无法到达终点，输出 -1
    }
}

javaScript

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

async function readInput() {
    let lines = [];
    for await (const line of rl) {
        lines.push(line);
    }
    return lines;
}

(async function main() {
    let lines = await readInput();
    let [n, start, end] = lines[0].split(" ").map(Number);

    // 边界处理
    if (start === end) {
        console.log(0);
        return;
    }
    
    if (n === 0) {
        console.log(-1);
        return;
    }

    // 构建邻接表
    let graph = Array.from({ length: 100001 }, () => []);
    for (let i = 1; i <= n; i++) {
        let [from, to] = lines[i].split(" ").map(Number);
        graph[from].push(to);
    }

    // BFS 进行最短路径搜索
    let queue = [start]; // BFS 队列
    let visited = new Set();
    visited.add(start);
    let steps = 0;

    while (queue.length > 0) {
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let from = queue.shift();

            // 如果到达终点
            if (from === end) {
                console.log(steps);
                return;
            }

            for (let to of graph[from]) {
                if (!visited.has(to)) {
                    visited.add(to);
                    queue.push(to);
                }
            }
        }
        steps++;
    }

    console.log(-1); // 无法到达
})();

题目内容

星际漫游是需要通行证的，塔子收集多年，希望来一次跨越群星的路程，去到一个叫做蓝星的星球，听说那里有一个二字游戏，非常好玩。

很不幸的是，塔子只有若干星球之间的通行证，为了尽快到达心心念念的蓝星，塔子决定找你帮忙规划一下线路。这里规定星际漫游的耗时与经历的星球数成正比。

规定，所有的星球都被编号，从1开始。

解答要求

时间限制:$C/C++800ms$,其他语言:$1600ms$ 内存限制:$C/C++60MB$，其他语言: $120MB$

输入

塔子拥有的通行证数目n以及塔子漫游的起点编号$m1$（$0 \leq m1 \leq 100000$）和终点编号$m2$（$0 \leq m2 \leq 100000$），

之后$n$行依次为$n$个通行证，每个通行证有两个数字，用空格隔开，分别表示该通行证允许通行的起点星球编号和终点星球编号。

注意，只能从起点星球飞往终点星球。

输出

计算塔子需要经过的星球数目，不包括起点星球，若无法到达目的地，则返回$-1$

样例

输入

1 1 2
1 2

输出

1

解释

本例表示:塔子有$1$个通行证，刚好直达蓝星，经过蓝星，故输出$1$。

样例2

输入

3 2 1
1 4 
3 2
3 5

输出

-1

解释

拥有的三个通行证无法保证塔子能从编号为$2$的星球到达编号为$1$的蓝星，塔子因玩不到二字游戏悲痛欲绝，因此结果为$-1$