90分求助,最后一个点WA
查看原帖
90分求助,最后一个点WA
312605
Megumimwf楼主2023/2/11 11:36
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
	ll x=0, f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch == '-'){
			f = -1;
		}
		ch = getchar();
	}
	while(ch>='0' && ch<='9'){
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}
inline void write(ll x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x/10);
	putchar(x%10+'0');
}

struct edge{
	ll to, dis, next;
};
edge e[100086];
ll n, m, head[100086], u, v, w, tot, dis[100086], vis[100086], sla[100086];
queue<ll> q;

inline void add(ll u, ll v, ll w){
	tot++;
	e[tot].next = head[u];
	e[tot].dis = -w;
	e[tot].to = v;
	head[u] = tot;
}

inline void spfa(ll s){
	memset(dis, 0x7f7f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	q.push(s);
	dis[s] = 0;
	vis[s] = 1;
	while(!q.empty()){
		int u = q.front();
		vis[u] = false;
		q.pop();
		for(int i=head[u];i;i=e[i].next){
			int v = e[i].to;
			if(dis[v] > dis[u] + e[i].dis){
				dis[v] = dis[u] + e[i].dis;
				sla[e[i].to]++;	
				if(!vis[v]){
					q.push(v);
					vis[v] = 1;
				}
				if(sla[e[i].to] > n){
					cout<<"Forever love";
					exit(0);
				}
			}
		}
	}
}

int main(){
	n = read(), m = read();
	for(int i=1;i<=m;++i){
		u = read(), v = read(), w = read();
		add(u, v, w);
	}
	spfa(1);
	cout<<dis[n];
	return 0;
}
2023/2/11 11:36
加载中...