#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？ (2360) hzoizjz 2014-11-05 20:10:54
  • Re:求大神指点，为什么WA？ (27) hzoizjz 2014-11-05 20:11:53
• Re:求大神指点，为什么WA？ (22) dongshimou 2014-11-25 15:07:27