codevs 1242 布局（查分约束+SPFA）

/*
查分约束.
给出的约束既有>= 又有<= 这时统一化成一种
Sb-Sa>=x 建边 a到b 权值为x 
Sb-Sa<=y => Sa-Sb>=-y 建边 b到a 权值为-y 
然后跑最短路 SPFA 判断到不了终点 判断负环的死循环. 

*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 20010
using namespace std;
int n,m1,m2,num,head[maxn],dis[maxn],f[maxn],use[maxn],falg;
struct node
{
    int v,t,pre;
}e[maxn];
int init()
{
    int x=0;char s;s=getchar();
    while(s<'0'||s>'9')s=getchar();
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x;
}
void Add(int from,int to,int dis)
{
    num++;
    e[num].v=to;
    e[num].t=dis;
    e[num].pre=head[from];
    head[from]=num;
}
void SPFA()
{
    queue<int>q;
    q.push(1);
    f[1]=1;
    dis[1]=0;
    use[1]++;
    while(!q.empty())
      {
          int k=q.front();
          q.pop();
          f[k]=0;
          if(use[k]>n)
            {
                falg=1;
                break;
          }
          for(int i=head[k];i;i=e[i].pre)
            if(dis[e[i].v]>dis[k]+e[i].t)
                 {
                   dis[e[i].v]=dis[k]+e[i].t;
                   if(f[e[i].v]==0)
                     {
                       q.push(e[i].v);
                  f[e[i].v]=1;
                  use[e[i].v]=use[k]+1;    
                }
            }
      }
}
int main()
{
    n=init();m1=init();m2=init();
    int x,y,z;
    for(int i=1;i<=m1;i++)
      {
          x=init();y=init();z=init();
          Add(x,y,z);
      }
    for(int i=1;i<=m2;i++)
      {
          x=init();y=init();z=init();
          Add(y,x,-z);
      }
    memset(dis,127,sizeof(dis));
    SPFA();
    if(dis[n]>1000000000)printf("-2");
    else if(falg==1)printf("-1");
    else printf("%d
",dis[n]);
    return 0;
}