409
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());
}
}
最後更新：2017-04-02 00:06:48