hud 5876 2016 ACM/ICPC Asia Regional Dalian Online

题意：给一个图给定一个点s 求补图中s点到达各个点的最短路

思路：从s点开始bfs 在图中与s点有连接的都是在补图中不能直接到达的点反之在补图中都是可以直接到达的点由此bfs （（（诡异的写法。。。

AC代码：

  1 #include "iostream"
  2 #include "string.h"
  3 #include "stack"
  4 #include "queue"
  5 #include "set"
  6 #include "map"
  7 #include "algorithm"
  8 #include "stdio.h"
  9 #include "math.h"
 10 #define ll long long
 11 #define mem(a) memset(a,0,sizeof(a))
 12 #define max(a,b) a > b ? a : b
 13 #define min(a,b) a < b ? a : b
 14 #define INF 20005
 15 using namespace std;
 16 
 17 
 18 int dis[200005];
 19 int vis[200005];
 20 
 21 vector<int>Node[200005];
 22 
 23 void Delete_Edge(int u,int v)
 24 {
 25     Node[u].push_back(v);
 26     Node[v].push_back(u);
 27 }
 28 
 29 void fun(int s,int n)
 30 {
 31     queue<int>Q;
 32     set<int> s1;
 33     set<int> s2;
 34     set<int> *ss;
 35     set<int> *ss1 = &s1;
 36     set<int> *ss2 = &s2;
 37     Q.push(s);
 38     dis[s] = 0;
 39     vis[s] = 1;
 40     for(int i=1; i<=n; i++)
 41         s1.insert(i);
 42     s1.erase(s);
 43 
 44     while(!Q.empty())
 45     {
 46         int r=Q.front();
 47         Q.pop();
 48         for(int i=0; i<Node[r].size(); i++)
 49         {
 50             if(!ss1->count(Node[r].at(i))) continue;
 51             ss2->insert(Node[r].at(i));  //未找到
 52             ss1->erase(Node[r].at(i));   //找到
 53         }
 54         set<int>::iterator it;
 55         for(it=ss1->begin(); it!=ss1->end(); it++)
 56         {
 57             if(!vis[*it])
 58             {
 59                 vis[*it] = 1;
 60                 dis[*it] = dis[r]+1;
 61                 Q.push(*it);
 62             }
 63         }
 64         ss1->clear();
 65         ss = ss1, ss1 = ss2, ss2 = ss;
 66     }
 67 }
 68 
 69 int main()
 70 {
 71     int n,m,t,s;
 72     scanf("%d",&t);
 73     while(t--)
 74     {
 75 
 76         mem(vis);
 77         scanf("%d%d",&n,&m);
 78         for(int i = 1; i <= n; ++i) dis[i] = 10000000;
 79         for(int i = 1; i <= n; ++i) Node[i].clear();
 80         for(int i=1; i<=m; i++)
 81         {
 82             int u,v;
 83             scanf("%d%d",&u,&v);
 84             Delete_Edge(u,v);
 85         }
 86         scanf("%d",&s);
 87         fun(s,n);
 88         int k = 0;
 89         for(int i=1; i<=n; i++)
 90         {
 91             if(i!=s)
 92             {
 93                 if(k==0)
 94                     printf("%d",dis[i]==10000000?-1:dis[i]);
 95                 else
 96                     printf(" %d",dis[i]==10000000?-1:dis[i]);
 97                 k++;
 98             }
 99         }
100         printf("
");
101     }
102     return 0;
103 }