poj 1511 Invitation Cards dijkstra+heap

     最近没有状态，不太难得一题，TLE了3次，WA了1次。

     这题主要就是要正向，逆向两次dijkstra,因为稀疏图，所以用heap优化有明显作用。

     注意会超出int范围，要用long long

    代码太挫了，越写越挫，估计到瓶颈期了

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
long long d[1000001];
bool vis[1000001];
int n;
int u[1000001],va[1000001];
int first[1000001],next[1000001],cnt,m;
int vf[1000001],vnext[1000001],vu[1000001],vvalue[1000001],vcnt;
int T;
struct node
{
    int v,x;
    friend bool operator <(node a,node b)
    {
        return a.v>b.v;
    }
    node(int a,int b)
    {
        v=a,x=b;
    }
    node()
    {
    }
};
void add(int vn,int un,int t)
{
    next[cnt]=first[vn];
    u[cnt]=un;
    va[cnt]=t;
    first[vn]=cnt++;

    vnext[vcnt]=vf[un];
    vu[vcnt]=vn;
    vvalue[vcnt]=t;
    vf[un]=vcnt++;
}
priority_queue<node> q;
void dijkstra(int x)
{
    memset(d,127,(n+1)*sizeof(d[0]));
    memset(vis,0,(n+1)*sizeof(vis[0]));
    while(!q.empty())q.pop();
    d[x]=0;
    q.push(node(d[x],x));
    int i,t,v;
    while(!q.empty())
    {
        v=q.top().x;q.pop();
        if(vis[v])continue;
        vis[v]=1;
        for(i=first[v];i!=-1;i=next[i])
        {
            if(d[u[i]]<=(t=d[v]+va[i]))continue;
            d[u[i]]=t;
            q.push(node(d[u[i]],u[i]));
        }
    }
}
void di2(int x)
{
    memset(d,127,(n+1)*sizeof(d[0]));
    memset(vis,0,(n+1)*sizeof(vis[0]));
    while(!q.empty())q.pop();
    d[x]=0;
    q.push(node(d[x],x));
    int i,t,v;
    while(!q.empty())
    {
        v=q.top().x;q.pop();
        if(vis[v])continue;
        vis[v]=1;
        for(i=vf[v];i!=-1;i=vnext[i])
        {
            if(d[vu[i]]<=(t=d[v]+vvalue[i]))continue;
            d[vu[i]]=t;
            q.push(node(d[vu[i]],vu[i]));
        }
    }
}
int main()
{
    int i,a,b,t;
    scanf("%d",&T);
    memset(next,-1,sizeof(next));
    memset(first,-1,sizeof(first));
    memset(vnext,-1,sizeof(vnext));
    memset(vf,-1,sizeof(vf));
    while(T--)
    {
        scanf("%d%d",&n,&m);
        cnt=0;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&t);
            add(a,b,t);
        }
        long long ans=0;
        dijkstra(1);
        for(i=2;i<=n;i++) ans+=d[i];
        di2(1);
        for(i=2;i<=n;i++) ans+=d[i];
        printf("%lld\n",ans);
        memset(next,-1,(m+1)*sizeof(next[0]));
        memset(first,-1,(n+1)*sizeof(first[0]));
        memset(vnext,-1,(m+1)*sizeof(vnext[0]));
        memset(vf,-1,(n+1)*sizeof(vf[0]));
    }
}