玄关,求助
  • 板块灌水区
  • 楼主0tAp
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/28 21:51
  • 上次更新2024/6/29 09:07:24
查看原帖
玄关,求助
758858
0tAp楼主2024/6/28 21:51

如代码所示,如果直接在solve里面调用spfa函数就过不了,但把spfa里面的直接写在solve里面就过了,这是为什么?

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
using namespace std;
#define xx return
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
const int N=5e4+10;

int h[N],e[N*2],ne[N*2],edge[N*2],idx=0;
int n,m;
queue<int>q;
int cnt[N],d[N];
bool vis[N];
void add(int a,int b,int c)
{
	e[++idx]=b,ne[idx]=h[a],edge[idx]=c,h[a]=idx;
}

//void spfa()
//{
//	memset(d,-0x3f,sizeof d);
//	vis[0]=1;
//	d[0]=0;
//	q.push(0);
//	while(!q.empty())
//	{
//		int u=q.front();
//		q.pop();
//		vis[u]=0;
//		for(int i=h[u];i;i=ne[i])
//		{
//			int v=e[i],w=edge[i];	
//			if(d[v]<d[u]+w)
//			{
//				d[v]=d[u]+w;
//				if(!vis[v]){
//					vis[v]=1;
//					q.push(v);
//					cnt[v]++;
//					if(cnt[v]>=n){
//						puts("No");xx;
//					}	
//				}
//			}
//		}
//	}
//	puts("Yes");
//	xx;
//}

inline void solve()
{
	int n,m;
	scanf("%lld%lld",&n,&m);
	rep(i,1,m)
	{
		int t,u,v,c;scanf("%lld%lld%lld",&t,&u,&v);
		if(t==1){scanf("%lld",&c);add(v,u,c);}
		else if(t==2){scanf("%lld",&c);add(u,v,-c);}
		else{add(u,v,0),add(v,u,0);}
	}
	rep(i,1,n)add(0,i,0);
	//spfa();
	memset(d,-0x3f,sizeof d);
	vis[0]=1;
	d[0]=0;
	q.push(0);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=h[u];i;i=ne[i])
		{
			int v=e[i],w=edge[i];	
			if(d[v]<d[u]+w)
			{
				d[v]=d[u]+w;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
					cnt[v]++;
					if(cnt[v]>=n){
						puts("No");xx;
					}	
				}
			}
		}
	}
	puts("Yes");
	xx;
}

signed main()
{
	solve();
	xx 0;
}
2024/6/28 21:51
加载中...