80分,wa了6.7两个点,帮调谢谢
查看原帖
80分,wa了6.7两个点,帮调谢谢
744789
Big_Bishop楼主2023/7/7 09:41
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct edge{
	int to,nxt,w;
}e[40005];
int cnt,head[1005],dis[1005],num[1005];
int n,m;
bool vis[1005];
void add(int x,int y,int z){
	e[++cnt]={y,head[x],z};
	head[x]=cnt;
}
bool spfa(int s){
	queue<int> q;
	q.push(s);
	vis[s]=1;
	memset(dis,0,sizeof dis);
	memset(num,0,sizeof num);
	dis[s]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v]>dis[u]-e[i].w){
				dis[v]=dis[u]-e[i].w;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
					num[v]++;
					if(num[v]>n) return 1;
				}
			}
		}
	}
	return 0;
}
int main(){
	memset(head,-1,sizeof head);
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	int ans=0;
	if(spfa(1)){
		printf("Forever love");
		return 0;
	}
	ans=dis[n];
	if(spfa(n)){
		printf("Forever love");
		return 0;
	}
	ans=min(ans,dis[1]);
	printf("%d",ans);
	return 0;
}

谢谢

2023/7/7 09:41
加载中...