poj 3169 查分约束 判断负环

看了这个查分约束的博客 ： https://blog.csdn.net/my_sunshine26/article/details/72849441

套用最短路就可以了

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;

#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair

const int N  =3e4+4;
const int M  =1e5+5e4+3;
const int INF = 0x3f3f3f3f;

struct edge{
    int to,cost;
    int next;
};
edge es[M];
int num[N],vis[N],d[N],head[N];
int n,k;

void addedge(int u,int v,int c){
    es[k].to =v;
    es[k].cost =c;
    es[k].next = head[u];
    head[u] = k;
    k++;
}

void init(){
    k = 0;
    for(int i=1;i<=n;++i)d[i]=INF,vis[i]=0,num[i]=0;

    memset(head,-1,sizeof(head));
}

int spfa(){

    d[1]=0;vis[1]=1;
    num[1]=1;

    queue<int>Q;

    while(!Q.empty())Q.pop();

    Q.push(1);

    while(!Q.empty()){
        int u =Q.front();Q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1 ;i = es[i].next){
            int v = es[i].to;
            if(d[v]>d[u]+es[i].cost){
                d[v] = d[u]+es[i].cost;
                if(vis[v]==0){
                    num[v]++;
                    if(num[v]>n)return -1;
                    vis[v]=1;
                    Q.push(v);
                }
            }

        }
    }

    return d[n];
}


int main(){

    int ml,md;
    while(scanf("%d %d %d",&n,&ml,&md)!=EOF){

        int a,b,c;

        init();

        while(ml--){
             scanf("%d %d %d",&a,&b,&c);
             //b-a<=c
             addedge(a,b,c);
        }
        while(md--){
            scanf("%d %d %d",&a,&b,&c);
            //b-a>=c  a-b<=-c
            addedge(b,a,-c);
        }

        /*for(int i=1;i<=n;++i){
            addedge(i+1,i,0);
        }*/

        int f = spfa();
        if(f==-1)cout<<f<<endl;
        else {
            if(d[n]==INF)cout<<-2<<endl;
            else cout<<d[n]<<endl;
        }
    }
    return 0;
}