wa求助
查看原帖
wa求助
1033990
lw393楼主2025/1/18 21:26
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int xxx[N];
vector<int>G[N];
int vis[N], dis[N];
int n, m, k;

void bfs(){
    for(int i = 1; i <= n; i++) dis[i] = -1;
    queue<tuple<int, int, int> >q; // first for the begin second for the vertex third for dis
    for(int i = 1; i <= k; i++) q.push({xxx[i], xxx[i], 0});
    while(!q.empty()){
        auto [be, u, d] = q.front(); 
        q.pop();
        if(vis[u] && d > dis[u]) continue;
        if(dis[u] != -1) vis[u] = 1;
        //cout << be << ' ' << u << ' ' << d << '\n';
        for(auto v : G[u]){
            if(v == be) continue;
            //cout << u << ' ' << v << '\n';
            if(dis[v] == -1) { dis[v] = d + 1; q.push({be, v, d + 1});}
        }
    }
}

void solve(){
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i++){
        cin >> xxx[i];
    }
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs();
    for(int i = 1; i <= n; i++) cout << dis[i] << ' ';
}

int main(){
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
2025/1/18 21:26
加载中...