网上看到的spfa的实现,很清晰。Orz~~
#include <cstdio>
#include <cstring>
const int maxn = 10000+1;
const int maxnm = 100000+1;
class node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
public:
int l,to;
node * next;
};
template<class T>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class queue
{
private:
long N;
T* s;
long beg,end;
public:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
inline void init()
{
beg=end=0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
queue(long size):N(size),s(new T[size])
{
init();
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
inline void push(const T& item)
{
s[end]=item;
++end;
end%=N;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
inline T pop()
{
T res=s[beg];
++beg;
beg%=N;
return res;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
inline bool empty()
{
return beg==end;
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
node *f[maxnm];
int n,m,s,t,ans;
int dist[maxn];
bool p[maxn];//判断点是否在队列当中
inline void init()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
FILE *fin = fopen("sssp.in","r");
int i,j,p1,p2,len;
node *tp;
fscanf(fin,"%d%d",&n,&m);
for (i = 1 ; i <= m ; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
fscanf(fin,"%d%d%d",&p1,&p2,&len);
tp = new node;
tp -> l = len;
tp -> to = p2;
tp -> next = f[p1];
f[p1] = tp;
}
fscanf(fin,"%d%d",&s,&t);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline void work()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j,k;
node * tp;
queue <int> que(n+1);
que.init();
memset(dist,126,sizeof(dist));
dist[s] = 0;
que.push(s);
p[s] = true;
do
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
i = que.pop();
tp = f[i];
p[i] = false; //p[i] = false 表示i点不在队列当中
while (tp!=NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (dist[i]+tp->l<dist[tp->to])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dist[tp->to] = dist[i]+tp->l;
if (!p[tp->to]) //如果tp->to没有在队列当中,那就将它加进去
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
que.push(tp->to);
p[tp->to] = true;
}
}
tp = tp->next;
}
}while (!que.empty());
}
inline void print()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
FILE *fout = fopen("sssp.out","w");
fprintf(fout,"%d\n",dist[t]);
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
init();
work();
print();
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
还有一种实现方法用了STL的queue,构图的方法很好是一个一维的加一个p数组
#include <iostream>
#include <queue>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const long MAXN=10000;
const long lmax=0x7FFFFFFF;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
long v;
long next;
long cost;
}Edge;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Edge e[MAXN];
long p[MAXN];
long Dis[MAXN];
bool vist[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
queue<long> q;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long m,n;//点,边
void init()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
long i;
long eid=0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(vist,0,sizeof(vist));
memset(p,-1,sizeof(p));
fill(Dis,Dis+MAXN,lmax);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while (!q.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
q.pop();
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for (i=0;i<n;++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
long from,to,cost;
scanf("%ld %ld %ld",&from,&to,&cost);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
e[eid].next=p[from];
e[eid].v=to;
e[eid].cost=cost;
p[from]=eid++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//以下适用于无向图
swap(from,to);
e[eid].next=p[from];
e[eid].v=to;
e[eid].cost=cost;
p[from]=eid++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void print(long End)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
//若为lmax 则不可达
printf("%ld\n",Dis[End]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void SPF()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
init();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
long Start,End;
scanf("%ld %ld",&Start,&End);
Dis[Start]=0;
vist[Start]=true;
q.push(Start);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while (!q.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
long t=q.front();
q.pop();
vist[t]=false;
long j;
for (j=p[t];j!=-1;j=e[j].next)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
long w=e[j].cost;
if (w+Dis[t]<Dis[e[j].v])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
Dis[e[j].v]=w+Dis[t];
if (!vist[e[j].v])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
vist[e[j].v]=true;
q.push(e[j].v);
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
print(End);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while (scanf("%ld %ld",&m,&n)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
SPF();
}
return 0;
}