Poj1511

题目大意:让你求出从原点到其他各个点来回的最短路径之和。

算法思想：首先正向建图，求出原点到各个点之间最短路径之和，在反向建图，再求一遍原点到各个点之间最短路之和（可以看做是各个点到远点的最短路，因为这时候原点到各个点的距离==各个点到原点的距离，这道题昨天不知道什么原因，wa了不下10次，今天上午一样的算法，一样的写法，重新写一遍 。。1A也是醉了）.。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF 1e10
#define MAXN 1000050
int t;
int a,b,n,m,e;
long long cc,res;
typedef struct Edge
{
    int u;
    int v;
    long long c;
};
int head[MAXN],next[MAXN*2],dist[MAXN];
Edge edges[MAXN*2];
bool visited[MAXN];
void addNode(int u,int v,long long c)
{
    edges[e].u=u;
    edges[e].v=v;
    edges[e].c=c;
    next[e]=head[u];
    head[u]=e++;
}
bool relax(int u,int v,long long c)
{
    if(dist[v]>dist[u]+c)
    {
        dist[v]=dist[u]+c;
        return true;
    }
    return false;
}
long long spfa(int src)
{
    long long ans=0;
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++)
    {
        dist[i]=INF;
    }
    dist[src]=0;
    queue<int>que;
    que.push(src);
    visited[src]=true;
    while(!que.empty())
    {
        int q=que.front();
        que.pop();
        visited[q]=false;
        for(int i=head[q];i+1;i=next[i])
        {
            if(relax(q,edges[i].v,edges[i].c)&&!visited[edges[i].v])
            {
               visited[edges[i].v]=true;
               que.push(edges[i].v);
            }
        }

    }


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


}
int main()
{

    scanf("%d",&t);
    while(t--)
    {
        memset(head,-1,sizeof(head));
        memset(next,-1,sizeof(next));
        e=1;
        res=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%lld",&a,&b,&cc);
            addNode(a,b,cc);
        }

        res+=spfa(1);
        memset(head,-1,sizeof(head));
        memset(next,-1,sizeof(next));
        e=1;
        for(int i=1;i<=m;i++)
        {
            addNode(edges[i].v,edges[i].u,edges[i].c);
        }

        res+=spfa(1);

        printf("%lld\n",res);
    }
    return 0;

}