多源点到单点最短路（这个题把我目前会的最短路的优化全给整上了 ：）

题目链接：https://vjudge.net/contest/66569#problem/J

题目大意： 给你站点n和人数p，让你求p个人从第一个点到其余点的花费总额和回来的路程的总额，求最小花费。

具体思路：建两个图，一个正向求去的花费最小，一个反向求回来的花费最小。

一开始用vector和spfa，tle。后来改成vector和迪杰斯特拉的堆优化，tle。最后，迪杰斯特拉的堆优化加上前向星，终于过了。。。。

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stdio.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
# define maxn 1000000+100
//ll vis[maxn];
ll n,m;
ll num1,num2;
//vector<pair<ll,ll > >wakaka1[maxn];
//vector<pair<ll,ll > >wakaka2[maxn];
ll head1[maxn];
ll head2[maxn];
struct node
{
    ll to;
    ll cost;
    ll ne;
} w1[maxn],w2[maxn];
void add1(ll u,ll v,ll w)
{
    w1[++num1].ne=head1[u];
    w1[num1].to=v;
    w1[num1].cost=w;
    head1[u]=num1;
}
void add2(ll u,ll v,ll w)
{
    w2[++num2].ne=head2[u];
    w2[num2].to=v;
    w2[num2].cost=w;
    head2[u]=num2;
}
void init()
{
    for(int i=1; i<=n; i++)
    {
        head1[i]=-1;
        head2[i]=-1;
    }
    num1=0,num2=0;
}
ll spfa(node w[],ll head[])
{
    ll dis[maxn];
    for(int i=1; i<=n; i++)
        dis[i]=inf;
    dis[1]=0;
    priority_queue<ll,vector<ll>,greater<ll> >q;
    q.push(1);
    while(!q.empty())
    {
        ll top=q.top();
        q.pop();
        for(ll i=head[top]; i!=0; i=w[i].ne)
        {
            if(dis[top]+w[i].cost<dis[w[i].to])
            {
           // cout<<dis[top]<<" "<<w1[i].cost<<endl;
          //  cout<<i<<" "<<w1[i].to<<" "<<dis[w1[i].to]<<endl;
                dis[w[i].to]=dis[top]+w[i].cost;
               // cout<<dis[w1[i].to]<<endl;
                q.push(w[i].to);
            }
           // cout<<i<<endl;
        }
    }
    ll ans=0;
    for(int i=1; i<=n; i++)
    {
        ans+=dis[i];
    }
    return ans;
}
int main()
{
    ll T;
    scanf("%lld",&T);
    while(T--)
    {
        init();
        scanf("%lld%lld",&n,&m);
        for(ll i=1; i<=m; i++)
        {
            ll u,v,w;
            scanf("%lld%lld%lld",&u,&v,&w);
            add1(u,v,w);
            add2(v,u,w);
        }
        ll sum=spfa(w1,head1)+spfa(w2,head2);
        printf("%lld
",sum);
    }
    return 0;
}