/ Vijos / 讨论 / 魔塔 /

求大犇来看一看啊,一晚上了就最后一个点没过

#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;
}
好惨好惨

0 条评论

目前还没有评论...

信息

ID
1321
难度
8
分类
搜索 | 图结构 点击显示
标签
(无)
递交数
1004
已通过
132
通过率
13%
被复制
4
上传者