WA2,TLE1

链接

代码：先将所有边变负，两遍 BFS，确定哪些点在1到n的路径上，再跑 SPFA，若路径上有负环则输出 inf，否则输出负的最短路（即最长路）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const int N=1e3+5;
vector<pair<int,int> >e[N];
queue<int>q,q1,q2;
int d[N],cnt[N];
bool vis[N],cc[N],v1[N],v2[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) d[i]=1e15;
    while(m--){
        int a,b,v;
        cin>>a>>b>>v;
        e[a].push_back({b,-v});
    }
    q1.push(1);
    v1[1]=1;
    while(q1.size()){
        int u=q1.front();
        q1.pop();
        for(auto t:e[u]){
            int v=t.fi;
            if(!v1[v]){
                v1[v]=1;
                q1.push(v);
            }
        }
    }
    q2.push(n);
    v2[n]=1;
    while(q2.size()){
        int u=q2.front();
        q2.pop();
        for(auto t:e[u]){
            int v=t.fi;
            if(!v2[v]){
                v2[v]=1;
                q2.push(v);
            }
        }
    }
    d[1]=0,vis[1]=1;
    q.push(1);
    while(q.size()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto t:e[u]){
            int v=t.fi,w=t.se;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n&&v1[v]&&v2[v]){
                    cout<<"inf";
                    return 0;
                }
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    cout<<-d[n];
	return 0;
}