#include  < iostream >
#include 
< vector >

using   namespace  std;

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

int  n, m;
int  c[ 1010 ], sum[ 1010 ], dist[ 1010 ];
vector
< Edge >  ege;

bool  bellman(){
    memset( dist, 
0 sizeof (dist) );    
    
int  len =  ege.size();
    
for int  i =   0 ; i <  n;  ++ i ){
        
for int  j =   0 ; j <  len;  ++ j )
        
if ( dist[ ege[j].u ] +  ege[j].w <  dist[ ege[j].v ] )
        dist[ ege[j].v ]
=  dist[ ege[j].u ] +  ege[j].w;
    }
    
bool  flag =   false ;
    
for int  j =   0 ; j <  len;  ++ j )
    
if ( dist[ ege[j].u ] +  ege[j].w <  dist[ ege[j].v ] )
    
return   false ;
    
    
return   true ;
}

int  main(){
    
while ( scanf( " %d%d " , & n, & m) !=  EOF ){
        memset( sum, 
0 sizeof (sum) );
        
for int  i =   1 ; i <=  n;  ++ i ){
             scanf(
" %d " , c +  i );
             sum[i]
=  sum[i - 1 ] +  c[i];
             ege.push_back( Edge( i
- 1 , i, c[i] ) );
             ege.push_back( Edge( i, i
- 1 0  ) );
        }
        
int  u, v, w;
        
while ( m --  ){
            scanf(
" %d%d%d " , & u, & v, & w );
            u
-- ;
            ege.push_back( Edge( v, u, 
- w ) );
            ege.push_back( Edge( u, v, sum[v]
-  sum[u] ) );
        }
        
if ! bellman() ) puts( " Bad Estimations " );
        
else              printf( " %d\n " ,dist[n] -  dist[ 0 ] );
        
        ege.clear();
    }
    
    
return   0 ;
}
posted on 2009-07-11 15:32 Darren 阅读(285) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理