邻接表实现，单源最短路径

    本篇文章，参考了y990041769同学的blog，他的博客地址如下[http://blog.csdn.net/y990041769/article/details/18367665]
    受他启发，这道题实际上从1出发到某个点，以及从此点回到1的最短距离。其实感觉只要建图，跑一遍spfa之后，再逆序跑一遍spfa就好了，可是在建图的时候坑死一大片，建图的时候用vector是会t的，虽然本题给了8s(Orz!)
    参考邻接表的模板，写了一个能过的版本，现在分享出来。
    先上模板：

///模板一，建图和保存节点信息

int H[N];  //存头节点 
struct   //记录节点信息 
{  
    int v;  ///相当于节点的终点
    int count;  ///相当于边权
    int next;  ///记录当前节点和下一个节点的关系
}E[N];  

int T,n,m,top;  

void Readmap(int m)  //读图 
{  
    memset(H,-1,sizeof(H));  
    int top=0;  
    for(int i=0;i<m;i++){  
        scanf("%d%d%d",&x[i],&y[i],&c[i]);  
        E[top].v=y[i];E[top].count=c[i];  
        E[top].next=H[x[i]];  
        H[x[i]]=top++;  
    }  
}  

///邻接表spfa模板

long long SPFA(int st)
{
    for(int i=1;i<=n;i++)
        sp[i]=inf;
    sp[1]=0;
    queue<int> q;
    q.push(st);
    while(!q.empty())
    {
        int kai=q.front();q.pop();
        for(int i=H[kai];i!=-1;i=E[i].next)
        {
            if(sp[E[i].v]>E[i].count+sp[kai]){
                sp[E[i].v]=E[i].count+sp[kai];
                q.push(E[i].v);
            }
        }
    }    ///spfa已经讲过，这里不再赘述
    long long ans=0;
    for(int i=1;i<=n;i++)
        ans+=sp[i];
    return ans;
}

///@zhangxiaoyu
///2015/8/10

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 1000005
#define INF 0x3f3f3f3f
typedef long long LL;

int x[maxn],y[maxn],c[maxn],sp[maxn];
int head[maxn];   ///保存头结点，即哪些边是与当前节点连接

struct node{ ///记录节点信息
   int v;    ///相当于终点
   int cnt;  ///相当于len
   int next;  ///记录此节点和下一个节点的关系
};

struct node E[maxn];
int n,m;

void input1()
{
    int top=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&c[i]);
        E[top].v=y[i];
        E[top].cnt=c[i];       ///权值
        E[top].next=head[x[i]];///记录当前节点前驱
        head[x[i]]=top++;
    }
}

void input2()
{
    int top=0;
    for(int i=1;i<=m;i++)
    {
        E[top].v=x[i];
        E[top].cnt=c[i];
        E[top].next=head[y[i]];
        head[y[i]]=top++;
    }
}

LL spfa(int st)
{
    int j;
    for(int i=1;i<=n;i++)
        sp[i]=INF;
    sp[1]=0;
    queue<int>qq;
    qq.push(st);
    while(!qq.empty())
    {
        j=qq.front();
        qq.pop();
        for(int i=head[j];i!=-1;i=E[i].next)
        {
            if(sp[E[i].v]>E[i].cnt+sp[j])
            {
                sp[E[i].v]=E[i].cnt+sp[j];
                qq.push(E[i].v);
            }
        }
    }
    LL ans=0;
    for(int i=1;i<=n;i++)
        ans+=sp[i];
    return ans;
}

int main()
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        LL ans=0;
        int u=1;
        scanf("%d%d",&n,&m);
        memset(E,INF,sizeof(INF));
        memset(head,-1,sizeof(head));
        input1();
        ans+=spfa(u);
        memset(E,INF,sizeof(E));
        memset(head,-1,sizeof(head));
        input2();
        ans+=spfa(u);
        printf("%lld\n",ans);
    }
    return 0;
}