90pts求调,但是进行了两次判断负权环
查看原帖
90pts求调,但是进行了两次判断负权环
866621
yfl20130101楼主2025/8/3 09:27
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,cnt[1005],dis[1005];
bool vis[1005];
vector<pair<ll,ll> >g[1005];
bool spfa(ll s){
	queue<ll>q;
	memset(cnt,0,sizeof(cnt));
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[s]=0,vis[s]=true,q.push(1);
	while(q.size()){
		ll u=q.front();
		q.pop();
		vis[u]=false;
		for(auto x:g[u]){
			ll v=x.first,w=x.second;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>n){
					cout<<"Forever love";
					exit(0);
				}
				if(!vis[v]){
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
	return false;
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,-w});
	}
	spfa(1);
	ll tmp1=dis[n];
	spfa(n);
	ll tmp2=dis[1];
	cout<<min(tmp1,tmp2);
	return 0;
}
2025/8/3 09:27
加载中...