1 #include<stdio.h>  2 #include<iostream>  3 #include<algorithm>  4 #include<math.h>  5 #include<string.h>  6 #include<string>  7 #include<map>  8 #include<set>  9 #include<vector> 10 #include<queue> 11 using namespace std; 12 const int maxn = 2e5+5; 13 const int INF  = 0x3f3f3f3f; 14 const int A=INF; 15 const int B=1; 16 typedef long long LL; 17 int h[maxn],e; 18 LL dis[maxn]; 19 bool vis[maxn]; 20 int start; 21  22 struct Edge 23 { 24     int v,nxt,w; 25 } E[maxn<<1]; 26  27 void init() 28 { 29     e=0; 30     memset(h,-1,sizeof h); 31     memset(vis,false,sizeof vis); 32 } 33  34 void add(int u,int v,int w) 35 { 36     E[e].v = v; 37     E[e].w = w; 38     E[e].nxt = h[u]; 39     h[u]  = e++; 40 } 41  42 struct QNode 43 { 44     int v,c; 45     QNode(int _v,int _c) 46     { 47         v = _v; 48         c=_c; 49     } 50     bool operator < (const QNode &a) const 51     { 52         return c>a.c; 53     } 54 }; 55  56 void dijkstra(int n) 57 { 58     memset(dis,INF,sizeof dis); 59     priority_queue<QNode>Q; 60     dis[1] = 0; 61     Q.push(QNode(1,0)); 62     while(!Q.empty()) 63     { 64         QNode tmp = Q.top(); 65         Q.pop(); 66         int u = tmp.v; 67         if(vis[u]) continue; 68         vis[u] = true; 69         for(int i=h[u]; ~i; i=E[i].nxt) 70         { 71             int v = E[i].v; 72             int w = E[i].w; 73             if(vis[v]) continue; 74             if(dis[u]+w<dis[v]) 75             { 76                 dis[v] = dis[u]+w; 77                 Q.push(QNode(v,dis[v])); 78             } 79         } 80     } 81 } 82  83 void BFS(int n,LL val) 84 { 85     set<int>ta,tb; 86     queue<int>Q; 87     Q.push(start); 88     dis[start] = 0,dis[n] = INF; 89     for(int i=1; i<=n; i++){ 90         if(i==start) continue; 91         ta.insert(i); 92     } 93     while(!Q.empty()) 94     { 95         int u = Q.front(); 96         Q.pop(); 97         for(int i=h[u]; ~i; i=E[i].nxt) 98         { 99             int v = E[i].v;100             if(!ta.count(v)) continue;101             ta.erase(v);102             tb.insert(v);103         }104         for(set<int>::iterator it=ta.begin(); it!=ta.end(); it++)105         {106             Q.push(*it);107             dis[*it] = dis[u] + val;108         }109         ta.swap(tb);110         tb.clear();111     }112 }113 114 int main()115 {116     int N,M,T;117     int u,v;118     while(scanf("%d",&T)!=EOF)119     {120         while(T--)121         {122             scanf("%d%d",&N,&M);123             init();124             bool flag = false;125             for(int i=0; i<M; i++)126             {127                 scanf("%d%d",&u,&v);128                 add(u,v,A);129                 add(v,u,A);130 131             }132             scanf("%d",&start);133             dijkstra(N);134             BFS(N,B);135             bool first=0;136             for(int i=1;i<=N;i++)137             {138                 if(i==start) continue;139                 if(first) printf(" ");140                 printf("%d",dis[i]);141                 first=1;142             }143             printf("\n");144         }145     }146     return 0;147 }148 149 150 /*151 152 1153 2 0154 1155 156 */