70pts求助 玄关
查看原帖
70pts求助 玄关
772368
Wind_love楼主2024/2/29 16:55
#include<bits/stdc++.h>
using namespace std;
struct node{
	int v,w,nxt;
}a[210000];
int head[210000],vis[210000],cnt[210000],tot,d[210000];
int n,m;
void add(int u,int v,int w){
	a[tot++].w=w;
	a[tot].v=v;
	a[tot].nxt=head[u];
	head[u]=tot;
}
int fl=0;
queue<int> q;
void spfa(){
	vis[1]=1;
	memset(d,0x3f,sizeof d);
	d[1]=0;
	q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=0;
		if(cnt[x]>n){
			cout<<"Forever love";exit(0);
		}
		for(int i=head[x];i;i=a[i].nxt){
			int y=a[i].v,z=a[i].w;
			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				if(!vis[y]){
					q.push(y);
					vis[y]=1;
					cnt[y]++;
				}
			}
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,-w);
	}
	spfa();
	if(d[n]==0x3f3f3f3f)cout<<"";
	else cout<<d[n];
}
2024/2/29 16:55
加载中...