记录编号	168506	评测结果	AAAAAAAAAA
题目名称	[WC 2010模拟] 奶牛排队	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2015-07-04 23:34:08	内存使用	1.08 MiB

//ALGORIHTM::DC
//AUTHOR::STDAFX
 
#define MAXE 50000UL
#define MAXN 2000UL
#define INF 100000000L
 
#include <cstdio>
#include <cstring>
 
using namespace std;
 
bool SPFA();
 
struct Edge{
    int v,nx,w;
};
 
struct stack{
    int head,data[MAXE];
    inline int top(){
        return data[head];
    }
    inline bool empty(){
        return head==0;
    }
    inline void pop(){
        head--;
        return;
    }
    inline void push(int temp){
        data[++head]=temp;
        return;
    }
};
 
Edge edge[MAXE];
 
int n,ml,md,indgr[MAXN],headlist[MAXN],a,b,k,ec,dx[MAXN];
 
bool ex[MAXN];
 
stack sta;
 
int main(){
freopen("layout.in","r",stdin);
freopen("layout.out","w",stdout);
    scanf("%d%d%d",&n,&ml,&md);
    for(int i=1;i<=ml;i++){
        //a->b w=k;
        scanf("%d%d%d",&a,&b,&k);
        edge[++ec].v=b;
        edge[ec].w=k;
        edge[ec].nx=headlist[a];
        headlist[a]=ec;
    }
    for(int i=1;i<=md;i++){
        //b->a w=-k
        scanf("%d%d%d",&a,&b,&k);
        edge[++ec].v=a;
        edge[ec].w=-k;
        edge[ec].nx=headlist[b];
        headlist[b]=ec;
    }
    for(int i=1;i<n;i++){
        //i+1->i
        edge[++ec].v=i;
        edge[ec].w=0;
        edge[ec].nx=headlist[i+1];
        headlist[i+1]=ec;
    }
    if(!SPFA()){
        printf("-1");
    }
    else if(dx[n]>INF){
        printf("-2");
    }
    else{
        printf("%d",dx[n]);
    }
    return 0;
}
 
bool SPFA(){
    memset(dx,50,sizeof(dx));dx[1]=0;
    sta.push(1);
    while(!sta.empty()){
        k=sta.top();sta.pop();ex[k]=0;
        for(int i=headlist[k];i!=0;i=edge[i].nx){
            if(dx[edge[i].v]>dx[k]+edge[i].w){
                dx[edge[i].v]=dx[k]+edge[i].w;
                if(!ex[edge[i].v]){
                    indgr[edge[i].v]++;
                    if(indgr[edge[i].v]>n){
                        return false;
                    }
                    ex[edge[i].v]=1;
                    sta.push(edge[i].v);
                }
            }
        }
    }
    return true;
}