灵异事件,关于queue
  • 板块题目总版
  • 楼主ljcnoi
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/1/25 18:44
  • 上次更新2025/1/25 22:37:35
查看原帖
灵异事件,关于queue
1176197
ljcnoi楼主2025/1/25 18:44

为什么以下代码我连输入都无法完整输入,但在注释掉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;
}
 
2025/1/25 18:44
加载中...