为什么以下代码我连输入都无法完整输入,但在注释掉q.push(1)
之后就可以完成输入了呢(虽然删掉后是错误的)?求大佬们给一点queue的实用建议。
#include<bits/stdc++.h>
using namespace std;
struct EDGE
{
int to,d,next;
};
EDGE edge[5005];
int head[505],cnt;
void adde(int fr,int to,int d)
{
cnt++;
edge[cnt].to=to;
edge[cnt].next=head[fr];
edge[cnt].d=d;
head[fr]=cnt;
}
int t,n,m,w;
int tot[505],dis[505];
queue<int> q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
cnt=0;
memset(head,0,sizeof(head));
memset(tot,0,sizeof(tot));
memset(dis,0x7f,sizeof(dis));
while(!q.empty())
{
q.pop();
}
cin>>n>>m>>w;
for(int i=1;i<=m;i++)
{
int x,y,d;
cin>>x>>y>>d;
//cout<<x<<" "<<y<<" "<<d<<endl;
adde(x,y,d);
adde(y,x,d);
}
for(int i=1;i<=w;i++)
{
int x,y,d;
cin>>x>>y>>d;
adde(x,y,-d);
//cout<<x<<" "<<y<<" "<<d<<endl;
}
q.push(1);
dis[1]=0;
while(!q.empty())
{
int a=q.front();
q.pop();
for(int i=head[a];i;i=edge[i].to)
{
int b=edge[i].to,d=edge[i].d;
if(dis[a]+d<dis[b])
{
tot[b]++;
dis[b]=dis[a]+d;
q.push(b);
if(tot[b]>n)
{
cout<<"NO"<<"\n";
goto end;
}
}
}
}
cout<<"YES"<<"\n";
end:;
}
return 0;
}
注释掉第51行的q.push(1)
对比,可以完成输入
#include<bits/stdc++.h>
using namespace std;
struct EDGE
{
int to,d,next;
};
EDGE edge[5005];
int head[505],cnt;
void adde(int fr,int to,int d)
{
cnt++;
edge[cnt].to=to;
edge[cnt].next=head[fr];
edge[cnt].d=d;
head[fr]=cnt;
}
int t,n,m,w;
int tot[505],dis[505];
queue<int> q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
cnt=0;
memset(head,0,sizeof(head));
memset(tot,0,sizeof(tot));
memset(dis,0x7f,sizeof(dis));
while(!q.empty())
{
q.pop();
}
cin>>n>>m>>w;
for(int i=1;i<=m;i++)
{
int x,y,d;
cin>>x>>y>>d;
//cout<<x<<" "<<y<<" "<<d<<endl;
adde(x,y,d);
adde(y,x,d);
}
for(int i=1;i<=w;i++)
{
int x,y,d;
cin>>x>>y>>d;
adde(x,y,-d);
//cout<<x<<" "<<y<<" "<<d<<endl;
}
//q.push(1);
dis[1]=0;
while(!q.empty())
{
int a=q.front();
q.pop();
for(int i=head[a];i;i=edge[i].to)
{
int b=edge[i].to,d=edge[i].d;
if(dis[a]+d<dis[b])
{
tot[b]++;
dis[b]=dis[a]+d;
q.push(b);
if(tot[b]>n)
{
cout<<"NO"<<"\n";
goto end;
}
}
}
}
cout<<"YES"<<"\n";
end:;
}
return 0;
}