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

· · 题解

思路

这题可以直接把除 N 以外的每个点当作起点，然后求起点到 N 的距离，但是这样太慢了，我们可以看到这是一个无向图，而且终点都是 N，所以可以直接把 N 当作起点，求它到每个点的距离，这样就可以快速得到答案。

代码

#include <bits/stdc++.h>
#define ll long long
//#define rw() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifndef rw()
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

namespace FX {
    template<typename T> inline void r(T &in) {
        in = 0;
        bool bo = 0;
        char ch = getchar();
        while (!isdigit(ch)) {
            bo ^= (ch == '-');
            ch = getchar();
        }
        while (isdigit(ch))
            in = (in << 1) + (in << 3) + (ch ^ 48), ch = getchar();
        if (bo) {
            in = -in;
        }
    }
    template<typename T> inline void w(T out) {
        static char op[20];
        int top = 0;
        if (out < 0) {
            putchar('-');
            do {
                op[++top] = -(out % 10) + 48, out /= 10;
            } while (out);
        } else {
            do {
                op[++top] = out % 10 + 48, out /= 10;
            } while (out);
        }
        while (top)
            putchar(op[top--]);
        putchar(' ');
    }
    template<typename T, typename... Ts> inline void r(T &in, Ts &... ins) {
        r(in), r(ins...);
    }
    template<typename T, typename... Ts> inline void w(T out, Ts... outs) {
        w(out), w(outs...);
    }
    inline void w(const char *p) {
        while (*p) {
            putchar(*p++);
        }
    }
}
using namespace FX;
#undef getchar
#undef putchar
#endif
using namespace std;
const ll N = 106;
ll n, m, dis[N];
vector<ll>e[N];

int main() {
    r(n, m);
    while (m--) {
        ll x, y;
        r(x, y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    memset(dis, -1, sizeof dis);
    queue<ll>q;
    dis[n] = 0;
    q.push(n);
    while (q.size()) {
        ll a = q.front();
        q.pop();
        for (auto v : e[a]) {
            if (dis[v] == -1) {
                dis[v] = dis[a] + 1;
                q.push(v);
            }
        }
    }
    for (ll i = 1; i < n; i++) {
        w(dis[i]);
    }
    return 0;
}

时间复杂度

O(n)