【题解-洛谷】B4292 [蓝桥杯青少年组省赛 2022] 路线

题目：B4292 [蓝桥杯青少年组省赛 2022] 路线

题目描述

有一个旅游景区，景区中有 $N$ 个景点，景点以数字 $1$ 到 $N$ 编号，其中编号为 $N$ 的景点为游客服务中心所在地。景区中有 $M$ 条连接路线，每条路线连接两个景点。

已知：

1. 一个景点可以被多条路线连接；
2. 景点之间的连接路线都可以双向行走；

当给出 $N$ 个景点和 $M$ 条连接路线，及 $M$ 条路线的连接关系，请你计算出从编号 $1$ 到编号 $N-1$ 的每一个景点，到达游客服务中心至少需要经过几条路线。如果某个景点不能到达游客服务中心则输出 $-1$。

例如：

• 当 $N=5$，$M=4$ 时
• 4 条路线的连接关系为：$1\leftrightarrow 2$、$1\leftrightarrow 3$、$2\leftrightarrow 4$、$2\leftrightarrow 5$
• 则：
  • 景点 $1$ 到达景点 $5$（游客服务中心）至少经过 $2$ 条路线（路线 $2$，路线 $4$）
  • 景点 $2$ 到达景点 $5$ 至少经过 $1$ 条路线（路线 $4$）
  • 景点 $3$ 到达景点 $5$ 至少经过 $3$ 条路线（路线 $1$，路线 $2$，路线 $4$）
  • 景点 $4$ 到达景点 $5$ 至少经过 $2$ 条路线（路线 $3$，路线 $4$）

输入格式

第一行输入两个正整数 $N$ 和 $M$（$4\le N\le 100$，$1\le M\le 100$），$N$ 表示景点个数，$M$ 表示路线条数，两个正整数之间一个空格隔开。

接下来输入 $M$ 行，每行包括两个正整数 $S$，$E$（$1\le S\le N$，$1\le E\le N$，$S\ne E$），两个正整数之间一个空格隔开，表示编号 $S$ 和编号 $E$ 的两个景点有一条路线连接。

输出格式

一行输出多个整数。按照 $1$ 到 $N-1$ 的编号顺序，分别输出每个景点到达编号 $N$（游客服务中心），经过几条路线可以到达，如果某个景点不能到达则输出 $-1$，整数之间一个空格隔开。

输入输出样例 #1

输入 #1

5 4
1 2
1 3
2 4
2 5

输出 #1

2 1 3 2

代码

#include<iostream>
#include<cstring>

using namespace std;

const int MaxN = 100 + 10, MaxM = 100 + 10;
int N, M, h[MaxN], e[MaxM * 2], ne[MaxM * 2], idx, q[MaxN], hh, tt = -1, d[MaxN];

void init(){
    memset(h, -1, sizeof h);
}

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void init_queue(){
    hh = 0, tt = -1;
}

void insert(int x){
    q[++ tt] = x;
}

void dele(){
    hh ++;
}

bool isempty(){
    return hh > tt;
}

void bfs(){
    memset(d, -1, sizeof d);
    insert(N);
    d[N] = 0;

    while(!isempty()){
        int t = q[hh];
        dele();

        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] == -1){
                insert(j);
                d[j] = d[t] + 1;
            }
        }
    }
}
int main(){
    cin >> N >> M;
    init();
    while(M --){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bfs();
    for(int i = 1; i < N; i ++){
        cout << d[i] << " ";
    }
    return 0;
}

结果