rt

其实不用判负环，在spfa运行的时候，如果遇到负环，spfa会死循环。

但其实我们只需要卡时一下，如果运行时间超过$500ms$(因为要跑两遍)，就直接输出Forever love退出即可。

代码如下

#include<bits/stdc++.h>
using namespace std;
const long long MX_N=5010,MX_M=50100,INF=0x3f3f3f3f;
const long long sec=600;
struct node{
    long long next,to;
    long long w;
}edge[MX_M<<1];
long long head[MX_N],edge_cnt=0;
inline void add(long long x,long long y,long long w){
    node &i=edge[edge_cnt];
    i.w=w,i.to=y,i.next=head[x];
    head[x]=edge_cnt++;
}
long long dist[MX_N]={0};
bool vis[MX_N]={0};
long long s,t;
void spfa(){
    memset(dist,INF,sizeof(dist));memset(vis,0,sizeof(vis));
    queue<long long> qu;qu.push(s);vis[s]=1;dist[s]=0;
    long long ti=clock();
    while(!qu.empty()){
        if(clock()-ti>sec){
            printf("Forever love");
            exit(0);
        }
        long long now=qu.front();qu.pop();vis[now]=0;
        for(long long i=head[now];~i;i=edge[i].next){
            long long to=edge[i].to,w=edge[i].w;
            if(dist[to]>dist[now]+w){
                dist[to]=dist[now]+w;
                if(!vis[to]){
                    qu.push(to);
                    vis[to]=1;
                }
            }
        }
    }
}
signed main(){
    memset(head,-1,sizeof(head));
    long long n,m;scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=m;i++){
        long long x,y,w;scanf("%lld%lld%lld",&x,&y,&w);
        add(x,y,-w);
    }long long ans=INF;
    s=1,t=n;spfa();ans=min(ans,dist[t]);
    s=n,t=1;spfa();ans=min(ans,dist[t]);
    printf("%lld",ans);
}

违规紫衫