xdoj Problem 1047 - Let's SPFA

    一道很奸诈的水题

    奸诈之处在于如果是顺序存的一下就过了，但是如果是像用邻接表那样逆序的话，估计就只有TLE了……

下面给一个邻接表的顺序版……其实没必要

/*
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>
#include <vector>
#define INF 1E9
using namespace std;
#define Maxn 40010
#define Maxm 140010
int w[Maxm],u[Maxm],next[Maxm],cnt;
int first[Maxn],d[Maxn],last[Maxn];
int m,n;
bool in[Maxn];
queue<int> q;
void add(int vn,int un,int wn)
{
    if(first[vn]==-1)first[vn]=cnt;
    if(last[vn]!=-1) next[last[vn]]=cnt;
    last[vn]=cnt;
    next[cnt]=-1;
    u[cnt]=un;w[cnt]=wn;
    cnt++;
}
long long spfa()
{
    int i,now,ne,t,len,j;
    memset(in,0,sizeof(in));
    for(i=0;i<n;i++)d[i]=INF;
    d[0]=0;in[0]=1;q.push(0);
    while(!q.empty())
    {
        now=q.front();q.pop();
        in[now]=0;
        for(i=first[now];i!=-1;i=next[i])
        {
            ne=u[i];
            if(d[ne]<=(t=d[now]+w[i]))continue;
            d[ne]=t;
            if(in[ne])continue;
            in[ne]=1;q.push(ne);
        }

    }
    long long ans=0;
    for(i=1;i<n;i++) ans+=d[i];
    return ans;
}
int main()
{
    int v,u,w;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;
        memset(first,-1,sizeof(first));
        memset(last,-1,sizeof(last));
        while(m--)
        {
            scanf("%d%d%d",&v,&u,&w);
            add(v,u,w);
            add(u,v,w);
        }
        printf("%lld\n",spfa());
    }
}