今天终于用SPFA写出了第一个程序，感觉收获很大，从Dij到Floyed再到Bellmen，以及今天的SPFA，每一种算法背后都蕴藏着许多值得思考的地方。正因为研究了它们，才使得我的能力不断地获得了提高。
之前以为SPFA做为最短路问题最快的算法，想必代码定不好写，不过今天研究过才知道，SPFA的代码量远远不及Dij，这着实令人惊叹，原来最好的算法SPFA是如此的好写，呵呵 我想此算法在很大程度上可以完全代替之前的算法，以后再碰到最短路问题时，SPFA一定能成为首要的选择！
PS:由于是用邻接表来存储的，所以每次操作前要收回以前分配的内存，我尝试了收回和不收回两种方法，发现其实差别不大，如果纯粹是比赛的话，可能不收回反而会更好些（避免超时）。当然如果在实际应用中，应该切记内存的分配，否则软件可能会发生异常。
//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];//此邻接表用于存储正向图
node reversed_edge[MAX_DOTNUM];//此逆邻接表用于存储逆向图
void initial(node edge[])//邻接表的初始化，里面封装了回收上一次操作所分配之内存的操作
{
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()//每一个case的输入函数
{
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)//如果队列不空，则进行松弛操作，直到队列空为止
{
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;
}