hdu 5876 (补图BFS) Sparse Graph

题目：这里

题意：

相当于一开始给一个初始好了的无向完全图给你，然后给让你删除m条边，再给你一个点v，最后问你在剩下的图里从这个点v出发能到达所有边点的最小路径是多少？

一看是所有点的最小路径，一看就觉得是个bfs，记忆化搜一下然后加个优化什么的，由于数据不知道是个什么奇葩而且比赛中还改数据，所以很多人wa的莫名其妙，

过也过的莫名其妙，我虽然过了但觉得有点不靠谱，赛后看了https://async.icpc-camp.org/d/546-2016的题解思路写了一发，总感觉更靠谱一点。

之前自己过的，就是用set记录那删掉的m条边，dis[i]数组记录每个结点的最小路径，当所有的点都搜到过的时候就可以结束了

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<queue>

 using namespace std;

 const int M = 2e5 + ;

 set<int>s[M];

 int n;bool vis[M];

 int dis[M],ans;

 int min(int x,int y){return x<y?x:y;}

 struct node{

    int po,dis;

 };

 void bfs(int pos)

 {

     memset(vis,false,sizeof(vis));

     queue<node>p;

     node now,next;

     now.po=pos;now.dis=;

     p.push(now);

     vis[pos]=true;

     while (!p.empty()){

         now=p.front();

         p.pop();

         for (int i= ; i<=n ; i++){

             next.po=i;next.dis=now.dis+;

             if (next.po==now.po) continue;

             if (vis[next.po]) continue;

             bool flag=false;

             if (s[now.po].find(next.po)!=s[now.po].end())

                 flag=true;

             if (flag) continue;

             vis[next.po]=true;

             dis[next.po]=min(next.dis,dis[next.po]);

             p.push(next);ans++;

         }

         if (ans==n) return ;

     }

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while (t--){

         int m;

         scanf("%d%d",&n,&m);

         for (int i= ; i<=n ; i++) s[i].clear(),dis[i]=M;

         while (m--){

             int u,v;

             scanf("%d%d",&u,&v);

             s[u].insert(v);

             s[v].insert(u);

         }

         int pos;

         scanf("%d",&pos);

         ans=;

         bfs(pos);

          if (n!=pos){

         for (int i= ; i<=n ; i++){

             if (i==pos) continue;

             if (i!=n) printf("%d ",dis[i]);

             else printf("%d\n",dis[i]);

         }

         }

         else{

             for (int i= ; i<n ; i++){

                 if (i!=n-) printf("%d ",dis[i]);

                 else printf("%d\n",dis[i]);

             }

         }

     }

     return ;

 }

后来看了别人的思路自己写的

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<set>

#include<queue>

using namespace std;

const int M = 2e5 + ;

int n,di[M],head[M],cas;

struct Edge{

    int to,next;

}edge[M*];

void add(int u,int v)

{

    edge[++cas].next=head[u];

    edge[cas].to=v;

    head[u]=cas;

}

int min(int x,int y){return x<y?x:y;}

struct node{

   int po,dis;

};

void bfs(int pos)

{

    set<int>s,e;

    set<int>::iterator it;

    for (int i= ; i<=n ; i++) s.insert(i),di[i]=M;

    queue<node>p;

    s.erase(pos);

    node now,next;

    now.po=pos;now.dis=;

    p.push(now);

    while (!p.empty()){

        now=p.front();

        p.pop();

        for (int i=head[now.po] ; i ; i=edge[i].next){

            int v=edge[i].to;

            if (s.find(v)==s.end()) continue;

            s.erase(v);

            e.insert(v);

        }

        for (it=s.begin() ; it!=s.end() ; it++){

            next.po=*it;next.dis=now.dis+;

            di[next.po]=min(next.dis,di[next.po]);

            p.push(next);

        }

        s.swap(e);e.clear();

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    while (t--){

        int m;cas=;

        scanf("%d%d",&n,&m);

        memset(head,,sizeof(head));

        while (m--){

            int u,v;

            scanf("%d%d",&u,&v);

            add(u,v);add(v,u);

        }

        int pos;

        scanf("%d",&pos);

        bfs(pos);

        if (n!=pos){

        for (int i= ; i<=n ; i++){

            if (i==pos) continue;

            if (i!=n) printf("%d ",di[i]);

            else printf("%d\n",di[i]);

        }

        }

        else{

            for (int i= ; i<n ; i++){

                if (i!=n-) printf("%d ",di[i]);

                else printf("%d\n",di[i]);

            }

        }

    }

    return ;

}