hdu_1535 难度为3的水题一道~

水的一b。。。 20分钟就敲好了，，没想到tmd居然敢卡vector！！！纠结了，为什么用vector会超内存！！！为什么啊！！！！！！！搞的我去鸟神的blog学了个静态邻接表，用的真变扭！！！不过还好，虽蛋疼但能ac。。。。。

#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<cmath>
using namespace std;
const int maxn = 1000011;
const int inf = 0x3f3f3f3f;
struct zz
{
    int to;
    int from;
    int cost;
    int next;
}zx,tz,g[maxn],g2[maxn];
int head[maxn];
int head2[maxn];
int e1,e2;
int t,p,q,now,cgo,cback,temp,sum,sum2,tv;
//vector<zz>g[maxn];
//vector<zz>g2[maxn];
queue<int>Q;
int go[maxn];
int back[maxn];
bool vis[maxn];

inline void init()
{
    memset(head,0,sizeof(head));
    memset(head2,0,sizeof(head2));
    for(int i=1;i<=p;i++)
    {
        go[i]=inf;
        back[i]=inf;
    }
    e1=1;
    e2=1;
    return ;
}
inline void add()
{   
    zx.next=head[zx.from];
    head[zx.from]=e1;
    g[e1++]=zx;
    return;  
}
inline void add2()
{
    zx.next=head2[zx.to];
    head2[zx.to]=e2;
    g2[e2++]=zx;
    return;   
}

void spfa()
{
    while(!Q.empty())
    {
        Q.pop();
    }  
    memset(vis,false,sizeof(vis));   
    go[1]=0;
    Q.push(1);
    vis[1]=true;
    while(!Q.empty())
    {       
        now=Q.front();
        Q.pop();  
        tv=head[now];
        while(tv)
        {
            temp = g[tv].to;
            cgo = g[tv].cost + go[now];
            if( cgo < go[temp] )  
            {
                go[temp]=cgo;
                if(!vis[temp])
                {   
                    Q.push(temp);
                    vis[temp]=true;
                }
            }   
            tv=g[tv].next;   
        }    
        vis[now]=false;
    } 
    sum=0;        
    for(int x=1;x<=p;x++)
    {
        sum+=go[x];     
    }   
    return ;
}

void spfa2()
{
    while(!Q.empty()) 
    {
        Q.pop();
    }   
    memset(vis,false,sizeof(vis));
    Q.push(1);
    vis[1]=true;
    back[1]=0;
    while(!Q.empty())
    {
        now=Q.front();
        Q.pop();
        tv=head2[now];
        while(tv)
        {
            temp = g2[tv].from;
            cback = g2[tv].cost + back[now];
            if(cback < back[temp] ) 
            {
                back[temp]=cback;
                if(!vis[temp])
                {
                    Q.push(temp);
                    vis[temp]=true;
                }
            }
            tv=g2[tv].next;
        }
        vis[now]=false;
    }     
    sum2=0;              
    for(int x=1;x<=p;x++)
    {
        sum2+=back[x];        
    }
    return ;
}

int main()
{
    cin>>t;
    
    while(t--)
    {
        cin>>p>>q;
        init();
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d%d",&zx.from,&zx.to,&zx.cost);
            add();
            add2();
        }
        spfa();
        spfa2();
        printf("%d\n",sum+sum2);
    }     
    return 0;
}