SPFA求解

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
const int M=10005+10005+1005;
const int INF=0x3f3f3f3f;

int n, m1, m2, E=0;
int head[N], cnt[N], dist[N];
bool vis[N];

struct Edge{int v, w, ne;}e[M];

// 判环&求SSSP
inline void add(int a, int b, int c){
    e[E].v=b;
    e[E].w=c;
    e[E].ne=head[a];
    head[a]=E++;
}

bool spfa(int k){
    memset(cnt, 0x00, sizeof cnt);
    memset(vis, 0x00, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    for(int i=1; i<=k; ++i){
        q.push(i);
        vis[i]=true;
        dist[i]=0;
    }

    while(!q.empty()){
        int node=q.front(); q.pop(); vis[node]=false;
        for(int i=head[node]; ~i; i=e[i].ne){
            int v=e[i].v;
            if(dist[v]>dist[node]+e[i].w){
                dist[v]=dist[node]+e[i].w;
                cnt[v]=cnt[node]+1;
                if(cnt[v]==n) return true;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    return false;
}

int main(){
    memset(head, -1, sizeof head);
    cin>>n>>m1>>m2;
    int a, b, c;
    for(int i=0; i<m1; ++i){
        cin>>a>>b>>c;
        if(a>b) swap(a, b); // 部分OJ未保证数据有序
        add(a, b, c);
    }
    for(int i=0; i<m2; ++i){
        cin>>a>>b>>c;
        if(a>b) swap(a, b);
        add(b, a, -c);
    }
    for(int i=1; i<n; ++i){
        add(i+1, i, 0);
    }

    if(spfa(n)) {cout<<-1<<endl; return 0;} // 存在负环
    else{
        spfa(1);
        if(dist[n]==INF) {cout<<-2<<endl; return 0;}
        else cout<<dist[n]<<endl;
    }


    return 0;
}