#include  < stdio.h >
#include 
< stdlib.h >
#include 
< string .h >

#define  N 1005
#define  inf 1<<29

struct  Edge{
    
int  u, v, d;
    Edge( 
int  a =   0 int  b =   0 int  c =   0  ):
        u(a), v(b), d(c) {}
};

int  n, ml, md, s =   0 ;
Edge  ege[
20010 ];
int  dist[N];

int  bell_man(){
    
for int  i =   1 ; i <=  n;  ++ i ) dist[i] =  inf;
    dist[
1 ] =   0 ;
    
    
int  flag =   0 ;
    
for int  i =   1 ; i <=  n;  ++ i ){
        flag
=   0 ;
        
for int  j =   0 ; j <  s;  ++ j ){
            
int  u =  ege[j].u, v =  ege[j].v, w =  ege[j].d;
            
if ( dist[u] +  w <  dist[v] ) dist[v] =  dist[u] +  w, flag =   1 ;
        }
        
if ! flag )  break ;
    }
    
if ( flag )  return   - 1 ;
    
else   if ( dist[n] ==  inf )  return   - 2 ;
    
else   return  dist[n];
}

int  main(){
    scanf(
" %d%d%d " , & n, & ml, & md );
    
int  u, v, d;
    
while ( ml --  ){
        scanf(
" %d%d%d " , & u, & v, & d );
        ege[s
++ ] =  Edge( u, v, d );
    }
    
while ( md --  ){
        scanf(
" %d%d%d " , & u, & v, & d );
        ege[s
++ ] =  Edge( v, u,  - d );
    }
    printf(
" %d\n " , bell_man() );

    
return   0 ;
}
posted on 2009-07-20 19:55 Darren 阅读(488) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理