- 魔塔
- 2015-10-24 00:55:38 @
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define maxn 51000
bool v[maxn];
long sis[maxn];
using std::vector;
using std::queue;
struct edge{long to,c;};
vector<edge> a;
vector<edge>::iterator itr;
edge e[maxn][1000];
queue<long> q;
void bfs(long s)
{
q.push(s);
long h;
while(!q.empty())
{
h=q.front();
q.pop();
for(long i=0;i<sis[h];i++)
{
if(!v[e[h][i].to] && v[e[h][i].c])
{
q.push(e[h][i].to);
v[e[h][i].to]=true;
}
else if(!v[e[h][i].c] ) a.push_back(e[h][i]);
}
for(itr=a.begin();itr!=a.end();itr++)
{
if(!v[itr->to])
if(v[itr->c])
{
q.push(itr->to);
v[itr->to]=true;
itr=a.erase(itr);
if(itr==a.end())
break;
}
}
}
}
int main()
{
long n,m,j,a,b,c;
scanf("%ld%ld%ld",&n,&j,&m);
memset(v,0,sizeof(v));
memset(sis,0,sizeof(sis));
for(long i=1;i<=m;i++)
{
scanf("%ld%ld%ld",&a,&b,&c);
e[a][sis[a]].to=b;
e[a][sis[a]].c=c;
sis[a]++;
e[b][sis[b]].to=a;
e[b][sis[b]].c=c;
sis[b]++;
}
v[j]=true;
bfs(j);
for(long i=1;i<=n;i++)
printf("%ld:%s",i,v[i]?"Yes\n":"No\n");
return 0;
}
好惨好惨