70pts求助
查看原帖
70pts求助
194761
Isenthalpic楼主2020/5/30 11:36
#include<bits/stdc++.h>
#define ll long long 
#define inf (0x3f3f3f3f)
using namespace std;
const int N=1e3+10;
const int M=2e4+10;
queue<int>q;
int n,m,tot,cnt[N],ans=inf;bool vis[N];
int pre[M],now[M],to[M],val[M],dis[N];
void add(int x,int y,int z)
{
	pre[++tot]=now[x];
	to[tot]=y;val[tot]=z;
	now[x]=tot;
}
void spfa(int st)
{
	for(int i=1;i<=n;i++)
		dis[i]=inf,vis[i]=0,cnt[i]=0;
	q.push(st);vis[st]=1;dis[st]=0;
	while(!q.empty())
	{
		int u=q.front();q.pop();vis[u]=0;
		for(int i=now[u],v=to[i],z=val[i];i;i=pre[i])
			if(dis[u]+z<dis[v])
			{
				dis[v]=dis[u]+z;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>n){
					printf("Forever love");
					exit(0);
				}
				if(!vis[v])vis[v]=1,q.push(v);
			}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,l;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&l);
		add(u,v,-l);
	}
	spfa(1);ans=min(dis[n],ans);
	spfa(n);ans=min(dis[1],ans);
	printf("%d",ans);
	return 0;
}
2020/5/30 11:36
加载中...