80,求调
  • 板块P2136 拉近距离
  • 楼主qb1_1
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/11 09:15
  • 上次更新2023/11/3 04:34:22
查看原帖
80,求调
711159
qb1_1楼主2023/8/11 09:15

#include<bits/stdc++.h>
#define maxn 20005
using namespace std;
int u,v,w;
int cnt[maxn],vis[maxn],d[maxn],n,m;
int head[maxn],ver[maxn],Next[maxn],edge[maxn];
int g;
int tot=0;
queue<int>q;
void add(int x,int y,int z){
	ver[++tot]=y;
	edge[tot]=z;
	Next[tot]=head[x];
	head[x]=tot;
}
bool spfa(int qb){
	memset(cnt,0,sizeof(cnt));
	memset(vis,0,sizeof(vis));
	memset(d,0x3f,sizeof(d));
	d[qb]=0;
	q.push(qb);
	vis[qb]=1;
	while(q.size()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i];
			if(d[y]>d[x]+edge[i]) {
				d[y]=d[x]+edge[i];
				cnt[y]=cnt[x]+1;
				if(cnt[y]>=n) return true;
				if(!vis[y]) {
					q.push(y);
					vis[y]=1;
				}
			}
		}
	}
	return false;
}
int main(){
		tot=0;
		cin>>n>>m;
		for(int j=1;j<=m;j++){
			cin>>u>>v>>w;
		add(u,v,-w);
		}
	bool n1=spfa(1);
	int bmp=d[n];
	if(n1&&spfa(n))
		cout<<"Forever love";
		else cout<<min(bmp,d[1]);
}
2023/8/11 09:15
加载中...