python/TangDou/LanQiaoBei/LanQiaoBei13ShengSai_ZJ_II/5_bfs_2.cpp

#include <bits/stdc++.h>
/**
 5 4
 1 2
 1 3
 2 4
 2 5

 答案
 2 1 3 2

 bfs求的是无权图或边权相等图的最短路径算法
*/
using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N]; // 邻接矩阵装图
int f[N];    // 离n点的距离
bool st[N];  // 是不是走过

void bfs() {
    queue<PII> q;   // PII: first sencond
    q.push({n, 0}); // first:n号点是起点,second:离出发点的距离
    st[n] = true;
    while (q.size()) {
        auto u = q.front();
        q.pop();
        for (int i = 1; i < n; i++)
            // 1、没走过
            // 2、有路可走
            if (!st[i] && g[u.first][i] != INF) {
                f[i] = u.second + 1;
                q.push({i, f[i]});
                st[i] = true;
            }
    }
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g); // 初始化每两个点之间的距离无穷大
    memset(f, -1, sizeof f);
    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    bfs();
    for (int i = 1; i < n; i++)
        cout << f[i] << " ";
    return 0;
}