POJ1511 SPFA

第一次做SPFA,本来觉得会很难很难写，所以一直都没有去涉及这个方面的题目。在FUZHOU网络赛上遇到了属于SPFA算法的题目，可是我却完全不知道。这次网络预选赛又是3题，还是没能去成现场赛... 最后一年了，我还是这么弱小，A题还是那么慢，所以要好好把握写题的速度尽量快起来！！

SPFA--Bellman-Ford的升级版，却是很好写的。另外几方面还是很省空间的。因为用边来存贮嘛，比如邻接矩阵，在稀疏图的条件下很快很暴力的就可以写出来。

算法我理解的很快，也只写了个裸的SPFA，没有去优化它，多做几个题练练手吧！

代码如下（不懂的可以问我哈）：

#include<stdio.h>
#include<queue>
#include<string.h>
#define INF 1234567891011
#define MAXN 1000005
using namespace std;struct Edge
{long v;long price;Edge *next;
}edge[2][MAXN],*ptr[2][MAXN];//存储两个图 另外实现邻接链表！
long dist[MAXN];int V,E;
int edgeNum;void addEdge(long a,long b,long c)
{Edge *p,*q;p=&edge[0][edgeNum];q=&edge[1][edgeNum];edgeNum++;p->v=b;p->price=c;p->next=ptr[0][a];ptr[0][a]=p;q->v=a;q->price=c;q->next=ptr[1][b];ptr[1][b]=q;
}void getEdges()
{int i,j;edgeNum=0;long a,b,c;for( i=1;i<=E;i++ ){scanf( "%lld %lld %lld",&a,&b,&c );addEdge(a,b,c);}
}bool used[MAXN];void SPFA( int graph,int start )
{memset( used,0,sizeof(used) );memset( dist,0x7F,sizeof(dist) );dist[start]=0;queue<int>queue;while( !queue.empty() )queue.pop();queue.push(start);used[start]=true;while( !queue.empty() ){long u=queue.front();queue.pop();Edge *p=ptr[graph][u];while( p!=NULL ){long w=p->price;long v=p->v;p=p->next;if( dist[v]>dist[u]+w ){dist[v]=dist[u]+w;if( !used[v] ){queue.push(v);used[v]=true;}}}used[u]=false;}
}int main()
{int T;scanf( "%d",&T );while( T-- ){scanf( "%d %d",&V,&E );int i,j,k;getEdges();long ans=0;for( k=0;k<2;k++ ){SPFA( k,1 );for( i=2;i<=V;i++ )ans+=dist[i];}printf( "%lld\n",ans );}return 0;
}