今天終于用SPFA寫出了第一個(gè)程序，感覺收獲很大，從Dij到Floyed再到Bellmen，以及今天的SPFA，每一種算法背后都蘊(yùn)藏著許多值得思考的地方。正因?yàn)檠芯苛怂鼈儯攀沟梦业哪芰Σ粩嗟孬@得了提高。
之前以為SPFA做為最短路問題最快的算法，想必代碼定不好寫，不過今天研究過才知道，SPFA的代碼量遠(yuǎn)遠(yuǎn)不及Dij，這著實(shí)令人驚嘆，原來最好的算法SPFA是如此的好寫，呵呵 我想此算法在很大程度上可以完全代替之前的算法，以后再碰到最短路問題時(shí)，SPFA一定能成為首要的選擇！
PS:由于是用鄰接表來存儲(chǔ)的，所以每次操作前要收回以前分配的內(nèi)存，我嘗試了收回和不收回兩種方法，發(fā)現(xiàn)其實(shí)差別不大，如果純粹是比賽的話，可能不收回反而會(huì)更好些（避免超時(shí)）。當(dāng)然如果在實(shí)際應(yīng)用中，應(yīng)該切記內(nèi)存的分配，否則軟件可能會(huì)發(fā)生異常。
//Coded by abilitytao
//Time:2009-04-10 22:49:58
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
#define MAX_NUM 1000000001
#define MAX_DOTNUM 1000001
int n,m;
queue<int>myqueue;
bool mark[MAX_DOTNUM];
__int64 dis[MAX_DOTNUM];
struct node
{
int v;
int w;
node *next;
}edge[MAX_DOTNUM];//此鄰接表用于存儲(chǔ)正向圖
node reversed_edge[MAX_DOTNUM];//此逆鄰接表用于存儲(chǔ)逆向圖
void initial(node edge[])//鄰接表的初始化，里面封裝了回收上一次操作所分配之內(nèi)存的操作
{
int i;
node *p;
node *q;
for(i=1;i<=n;i++)
{
p=&edge[i];
q=p->next;
while(q!=NULL)
{
p->next=q->next;
delete q;
q=p->next;
}
}
}
void input_case()//每一個(gè)case的輸入函數(shù)
{
int i;
for(i=1;i<=m;i++)
{
node *p;
node *q;
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
/**/////////////////////////
p=&edge[a];
q=new node;
q->v=b;
q->w=c;
q->next=p->next;
p->next=q;
/**/////////////////////////
p=&reversed_edge[b];
q=new node;
q->v=a;
q->w=c;
q->next=p->next;
p->next=q;
}
}
void spfa(node edge[])//SPFA部分
{
int i;
/**////////////////////////////////////////////////////////////////
memset(mark,false,sizeof(mark));
for(i=1;i<=n;i++)
dis[i]=MAX_NUM;
while(myqueue.size()!=0)
myqueue.pop();
/**////////////////////////////////////////////////////////////
dis[1]=0;
mark[1]=true;
myqueue.push(1);
while(myqueue.size()!=0)//如果隊(duì)列不空，則進(jìn)行松弛操作，直到隊(duì)列空為止
{
int temp=myqueue.front();
myqueue.pop();
mark[temp]=false;
node *p;
for(p=edge[temp].next;p!=NULL;p=p->next)
{
if(dis[p->v]>dis[temp]+p->w)
{
dis[p->v]=dis[temp]+p->w;
if(mark[p->v]!=true)
{
myqueue.push(p->v);
mark[p->v]=true;
}
}
}
}
}
int main()
{
int testcase;
int i,j;
__int64 sum;
scanf("%d",&testcase);
for(i=1;i<=MAX_DOTNUM-1;i++)
{
edge[i].v=i;
edge[i].w=0;
edge[i].next=NULL;
}
for(i=1;i<=MAX_DOTNUM-1;i++)
{
reversed_edge[i].v=i;
reversed_edge[i].w=0;
reversed_edge[i].next=NULL;
}
for(i=1;i<=testcase;i++)
{
sum=0;
scanf("%d%d",&n,&m);
initial(edge);
initial(reversed_edge);
input_case();
spfa(edge);
for(j=1;j<=n;j++)
sum+=dis[j];
spfa(reversed_edge);
for(j=1;j<=n;j++)
sum+=dis[j];
printf("%I64d\n",sum);
}
system("pause");
return 0;
}