2、总结:好题,把STL都过了一遍
题意:n个点组成的完全图,删去m条边,求点s到其余n-1个点的最短距离。
思路:把点分为两个集合,A为所有没有到达过的点,B为当前不可到达的点,每次拓展A中可到过的点加入队列。
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#define F(i,a,b) for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=,MAX=; int n,m,dis[N];
vector<int >vec[N]; void bfs(int s)
{
mes(dis,);
set<int >A,B;
FF(i,,n)if(i!=s)
A.insert(i);
queue<int >qu;
qu.push(s);
while(!qu.empty()){
int u=qu.front();
qu.pop();
for(int i=;i<vec[u].size();i++){ //注:vec从0开始
int v=vec[u][i];
if(A.count(v)){
A.erase(v); //集合删除、插入
B.insert(v);
}
}
for(set<int >::iterator it=A.begin();it!=A.end();it++){ //注:it!=A.end()结尾
dis[*it]=dis[u]+; //注:*it
qu.push(*it);
}
A.swap(B); //集合交换
B.clear(); }
} int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
FF(i,,n)vec[i].clear(); //注:vec[i].clear()
while(m--){
int u,v;
scanf("%d%d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
}
int s;
scanf("%d",&s);
bfs(s);
int flag=;
FF(i,,n){
if(i!=s){
if(flag)printf(" ");
else flag=;
printf("%d",dis[i]);
}
}
printf("\n");
} return ;
}