> #include <iostream>
> #include <stdlib.h>
> #include <math.h>
> #include <string.h>
> #include <vector>
> #include <queue>
> #define MAXV 1000006
> #define INF 0xfffffff
> using namespace std;
> 
> struct edge{
>        int val;
>        int to;
> };
> 
> vector <edge> e[MAXV];
> int dist[MAXV];
> queue <int> buff;
> bool visit[MAXV];
> int E,V;
> int a[MAXV],b[MAXV],l[MAXV];
> 
> void spfa( const int st )
> {
>      for( int i=1 ; i<=V ; i++ ){
>           dist[i] = INF;
>           if( i == st )
>               dist[i] = 0;
>           visit[i] = false;
>      }
>      visit[st] = true;
>      buff.push( st );
>      visit[st] = true;
>      while( !buff.empty() ){
>             int tmp = buff.front();
>             for( int i=0 ; i<(int)e[tmp].size() ; i++ ){
>                  edge *t = &e[tmp][i];
>                  if( dist[tmp] + t->to < dist[t->to] ){
>                      dist[t->to] = dist[tmp] + t->val;
>                      if( !visit[t->to] ){
>                          buff.push( t->to );
>                          visit[t->to] = true;
> 
>                  } 
>             }
>             visit[tmp] = false;
>             buff.pop();     
>      }
> }
> 
> 
> int main( )
> {
>     int cas;
>     scanf("%d",&cas);
>     while( cas-- ){
>            scanf("%d%d",&V,&E);
>            for( int i=0 ; i<E ; i++ ){
>                 scanf("%d%d%d",&a[i],&b[i],&l[i]);
>                 edge tmp;
>                 tmp.val = l[i];
>                 tmp.to = b[i];
>                 e[ a[i] ].push_back( tmp );
>            }
>            long long ans = 0 ;
>            spfa( 1 );
>            for( int i=1 ; i<=V ; i++ )                  
>                      ans += dist[i];
>            for( int i=1 ; i<=V ; i++ )
>                     e[i].clear();
>            for( int i=0 ; i<E ; i++ ){
>                     edge tmp;
>                     tmp.val = l[i];
>                     tmp.to = a[i];
>                     e[ b[i] ].push_back( tmp );     
>            }
>            spfa( 1 );
>            for( int i=1 ; i<=V ; i++ )
>                  ans += dist[i];  
>            for( int i=1 ; i<=V ; i++ )
>                     e[i].clear();
>            printf("%ld\n",ans);
>     }
>     //system("pause");
>     return 0;
> }

• Re:求大神指点，为什么WA？ (27) hzoizjz 2014-11-05 20:11:53