SPFA 80分求救
查看原帖
SPFA 80分求救
1124466
Tommyshizichen楼主2024/3/2 10:35
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5; 
int fi[N],to[N],nex[N],w[N],dis[N];
bool vis[N],flag;
int n,f,e,tot;
void add(int x,int y,int z){
	nex[++tot]=fi[x];
	fi[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
queue<int> q;
int cnt[100005];
void spfa(int s){
	for(int i=1;i<=n;++i)
		vis[i]=0,dis[i]=0x3f3f3f3f;	
	dis[s]=0;
	q.push(s);
	vis[s]=1;cnt[s]++;
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=0;
		for(int i=fi[u];i;i=nex[i]){
			int v=to[i];
			if(dis[v]>dis[u]+w[i]){
				dis[v]=dis[u]+w[i];
				if(++cnt[v]>=n) {						 
					flag=1;	return;
				} 
				if(!vis[v]){
					q.push(v);
					vis[v]=1;				
				}
			}
		}		
	}
}
int main()
{
	cin>>n>>f;
	for(int i=1;i<=f;i++) {
		int op,a,b,c;
		scanf("%d",&op);
		if (op==1)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,-c);
		}
		else if(op==2)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(b,a,c);
		}
		else if(op==3)
		{
			scanf("%d%d",&a,&b);
			add(a,b,0);
			add(b,a,0);
		}
	}
	spfa(1);
	if(flag==1) cout<<"No";
	else cout<<"Yes";
	return 0;
 } 
2024/3/2 10:35
加载中...