網上看到的spfa的實現，很清晰。Orz~~
#include <cstdio>
#include <cstring>
const int maxn = 10000+1;
const int maxnm = 100000+1;
class node
{
public:
int l,to;
node * next;
};
template<class T>
class queue{
private:
long N;
T* s;
long beg,end;
public:
inline void init(){
beg=end=0;
}
queue(long size):N(size),s(new T[size]){
init();
}
inline void push(const T& item){
s[end]=item;
++end;
end%=N;
}
inline T pop(){
T res=s[beg];
++beg;
beg%=N;
return res;
}
inline bool empty(){
return beg==end;
}
};
node *f[maxnm];
int n,m,s,t,ans;
int dist[maxn];
bool p[maxn];//判斷點是否在隊列當中
inline void init()
{
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++)
{
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);
}
inline void work()
{
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
{
i = que.pop();
tp = f[i];
p[i] = false; //p[i] = false 表示i點不在隊列當中
while (tp!=NULL)
{
if (dist[i]+tp->l<dist[tp->to])
{
dist[tp->to] = dist[i]+tp->l;
if (!p[tp->to]) //如果tp->to沒有在隊列當中，那就將它加進去
{
que.push(tp->to);
p[tp->to] = true;
}
}
tp = tp->next;
}
}while (!que.empty());
}
inline void print()
{
FILE *fout = fopen("sssp.out","w");
fprintf(fout,"%d\n",dist[t]);
}
int main()
{
init();
work();
print();
return 0;
}
還有一種實現方法用了STL的queue，構圖的方法很好是一個一維的加一個p數組
#include <iostream>
#include <queue>
using namespace std;
const long MAXN=10000;
const long lmax=0x7FFFFFFF;
typedef struct
{
long v;
long next;
long cost;
}Edge;
Edge e[MAXN];
long p[MAXN];
long Dis[MAXN];
bool vist[MAXN];
queue<long> q;
long m,n;//點,邊
void init()
{
long i;
long eid=0;
memset(vist,0,sizeof(vist));
memset(p,-1,sizeof(p));
fill(Dis,Dis+MAXN,lmax);
while (!q.empty())
{
q.pop();
}
for (i=0;i<n;++i)
{
long from,to,cost;
scanf("%ld %ld %ld",&from,&to,&cost);
e[eid].next=p[from];
e[eid].v=to;
e[eid].cost=cost;
p[from]=eid++;
//以下適用于無向圖
swap(from,to);
e[eid].next=p[from];
e[eid].v=to;
e[eid].cost=cost;
p[from]=eid++;
}
}
void print(long End)
{
//若為lmax 則不可達
printf("%ld\n",Dis[End]);
}
void SPF()
{
init();
long Start,End;
scanf("%ld %ld",&Start,&End);
Dis[Start]=0;
vist[Start]=true;
q.push(Start);
while (!q.empty())
{
long t=q.front();
q.pop();
vist[t]=false;
long j;
for (j=p[t];j!=-1;j=e[j].next)
{
long w=e[j].cost;
if (w+Dis[t]<Dis[e[j].v])
{
Dis[e[j].v]=w+Dis[t];
if (!vist[e[j].v])
{
vist[e[j].v]=true;
q.push(e[j].v);
}
}
}
}
print(End);
}
int main()
{
while (scanf("%ld %ld",&m,&n)!=EOF)
{
SPF();
}
return 0;
}