排队布局

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

const int N = 1005, M = 2 * 1e4 + 1010;

int n, m, k;
int h[N], e[M], ne[M], w[M], idx;
int cnt[N];
int q[N], dist[N];
bool st[N];

void add(int a,int b,int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa(int s){
    int hh = 0, tt = 0;
    q[tt ++ ] = s;
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    memset(cnt, 0, sizeof cnt);
    dist[s] = 0;
    while(hh != tt){
        int t = q[hh ++ ];
        if(hh == N) hh = 0;
        st[t] = false;
        for(int i = h[t];~i;i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true;
                if(!st[j]){
                    st[j] = true;
                    q[tt ++ ] = j;
                    if(tt == N) tt = 0;
                }
            }
        }
    }

    return false;
}

int main(){

    scanf("%d%d%d", &n, &m, &k);

    memset(h, -1, sizeof h);
    for(int i = 1;i < n;i ++ )
        add(i + 1, i, 0);
    int a, b, w;
    for(int i = 1;i <= m;i ++ ){
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
    }
    for(int i = 1;i <= k;i ++ ){
        scanf("%d%d%d", &a, &b, &w);
        add(b, a, -w);
    }

    if(spfa(n)) puts("-1");
    else{
        spfa(1);
        if(dist[n] == INF) puts("-2");
        else printf("%d\n", dist[n]);
    }

    return 0;
}