//============================================================================

// Name        : POJ.cpp

// Author      :

// Version     :

// Copyright   : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

/*

 * 使用优先队列优化Dijkstra算法

 * 复杂度O(ElogE)

 * 注意对vector<Edge>E[MAXN]进行初始化后加边

 */

const int INF=0x3f3f3f3f;

const int MAXN=1000010;

struct qnode

{

    int v;

    int c;

    qnode(int _v=0,int _c=0):v(_v),c(_c){}

    bool operator <(const qnode &r)const

    {

        return c>r.c;

    }

};

struct Edge

{

    int v,cost;

    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}

};

vector<Edge>E[MAXN];

bool vis[MAXN];

int dist[MAXN];

void Dijkstra(int n,int start)//点的编号从1开始

{

    memset(vis,false,sizeof(vis));

    for(int i=1;i<=n;i++)dist[i]=INF;

    priority_queue<qnode>que;

    while(!que.empty())que.pop();

    dist[start]=0;

    que.push(qnode(start,0));

    qnode tmp;

    while(!que.empty())

    {

        tmp=que.top();

        que.pop();

        int u=tmp.v;

        if(vis[u])continue;

        vis[u]=true;

        for(int i=0;i<E[u].size();i++)

        {

            int v=E[tmp.v][i].v;

            int cost=E[u][i].cost;

            if(!vis[v]&&dist[v]>dist[u]+cost)

            {

                dist[v]=dist[u]+cost;

                que.push(qnode(v,dist[v]));

            }

        }

    }

}

void addedge(int u,int v,int w)

{

    E[u].push_back(Edge(v,w));

}

int A[MAXN],B[MAXN],C[MAXN];

int main()

{

//    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    int n,m;

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i=0;i<m;i++)

            scanf("%d%d%d",&A[i],&B[i],&C[i]);

        for(int i=1;i<=n;i++)E[i].clear();

        for(int i=0;i<m;i++)addedge(A[i],B[i],C[i]);

        Dijkstra(n,1);

        long long ans=0;

        for(int i=1;i<=n;i++)ans+=dist[i];

        for(int i=1;i<=n;i++)E[i].clear();

        for(int i=0;i<m;i++)addedge(B[i],A[i],C[i]);

        Dijkstra(n,1);

        for(int i=1;i<=n;i++)ans+=dist[i];

        printf("%I64d\n",ans);

    }

    return 0;

}

版权声明：本文为博主原创文章，未经博主允许不得转载。