90分WA,求助SPFA跑最短路+判负环
  • 板块P2648 赚钱
  • 楼主银河AI
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/9/22 21:36
  • 上次更新2023/11/4 05:52:27
查看原帖
90分WA,求助SPFA跑最短路+判负环
209808
银河AI楼主2021/9/22 21:36

第二个点WA了,求助

#include<bits/stdc++.h>
#include<queue>
#define int long long
using namespace std;
const int N=3e2+1,M=6e2+1,inf=1e12;
int d,p,c,f;
struct edge{
	int to,ne,dis;
}e[M];
int adj[N],l;
inline void add(int x,int y,int z){
	e[++l].to=y;
	e[l].ne=adj[x];
	adj[x]=l;
	e[l].dis=z;
}
int vis[N],dis[N],cnt[N];
int flag=0;
queue<int> q;
inline void SPFA(int s){
	for(int i=0;i<=c;i++) dis[i]=inf,vis[i]=0;
	vis[s]=1;dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=0;
		
		for(int i=adj[x];i;i=e[i].ne){
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis){
				dis[y]=dis[x]+e[i].dis;
				cnt[y]++;
				if(cnt[y]>c){flag=1;return ;}
				if(!vis[y]) vis[y]=1,q.push(y); 
			}
		}
	}
}
signed main(){
	scanf("%lld%lld%lld%lld",&d,&p,&c,&f);
	for(int i=1;i<=c;i++) add(0,i,-d);
	for(int i=1;i<=p;i++){
		int x,y;
		scanf("%lld%lld",&x,&y);
		add(x,y,-d);
	}
	for(int i=1;i<=f;i++){
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z-d);
	}
	SPFA(0);
	if(flag) printf("orz");
	else{
		int minn=0;
		for(int i=1;i<=c;i++) minn=min(minn,dis[i]);
		printf("%lld",-minn);
	}
} 
2021/9/22 21:36
加载中...