HDU 5876 补图最短路-蒲公英云

HDU 5876 补图最短路

题意：给一个图，和起点s，求s在补图中到各个点的最短路。

分析：补图最短路，算是比较套路的一类题了，bfs+两个set维护邻接点和未扩展的点。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int N = 1e6+5;
int t,n,m,s,d[N];
vector<int> g[N];
void bfs() {
    queue<int> q;
    q.push(s);
    d[s] = 0;
    set<int> a,b;
    for(int i=1;i<=n;i++) a.insert(i);
    a.erase(s);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto v:g[u]) {
            if(!a.count(v)) continue;
            b.insert(v);///未扩展的点
            a.erase(v);///邻接点
        }
        for(auto it:a) {
            d[it] = d[u] + 1;
            q.push(it);
        }
        a = b;
        b.clear();
    }
    int f=0;
    for(int i=1;i<=n;i++) {
        if(i==s) continue;
        if(d[i]==inf) d[i] = -1;
        if(f) printf(" %d",d[i]);
        else printf("%d",d[i]);
        f=1;
    }
    printf("\n");
}
int main(){
    while(~scanf("%d",&t)) {
        while(t--) {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++) g[i].clear(),d[i]=inf;
            for(int i=1;i<=m;i++) {
                int u,v;
                scanf("%d%d",&u,&v);
                g[u].push_back(v);
                g[v].push_back(u);
            }
            scanf("%d",&s);
            bfs();
        }
    }
    return 0;
}