poj3169 Layout

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

using namespace std;

int n, m, head[10010], to[20020], nextt[20020], w[20020], tot = 1, vis[10010], d[10010], cnt[10010],md,ml;
bool flag;

void add(int x, int y, int c)
{
    w[tot] = c;
    to[tot] = y;
    nextt[tot] = head[x];
    head[x] = tot++;
}

void spfa(int u)
{
    queue <int> q;
    for (int i = 1; i <= n; i++)
        d[i] = 1000000000;
    d[u] = 0;
    vis[u] = 1;
    q.push(u);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = 0;
        for (int i = head[t]; i; i = nextt[i])
        {
            int v = to[i];
            if (d[v] > d[t] + w[i])
            {
                d[v] = d[t] + w[i];
                if (!vis[v])
                {
                    cnt[v]++;
                    if (cnt[v] > n)
                    {
                        flag = 0;
                        return;
                    }
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

int main()
{
    while (~scanf("%d%d%d",&n,&ml,&md))
    {
        flag = true;
        tot = 1;
        memset(head, 0, sizeof(head));
        memset(cnt, 0, sizeof(cnt));
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= ml; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);   //b - a <= c
        }
        for (int i = 1; i <= md; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(b, a, -c); // b - a >= c
        }
        spfa(1);
        if (flag == false)
            printf("-1\n");
        else
            if (d[n] == 1000000000)
                printf("-2\n");
            else
                printf("%d\n", d[n]);
    }

    return 0;
}