/*
对于菜鸟，第一次接触这种大型算法，应该抽出一大段时间研究,研究这个算法我认为要有DIJ和Floyd的铺垫。
搜集各路资料，大概有以下几个要点。
1.SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
（啊，亲，什么是Bellman-Ford？大致：1对每条边进行|V|-1次Relax操作;2如果存在(u,v)∈E使得dis[u]+w<dis[v],
则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。）
2.算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束(很重要啊亲,对于我这样编码能力很渣的很重要,重要在什么?关键词"队列""相连")。
3.伪代码
Procedure SPFA;
Begin
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do
begin
u:=dequeue(Q);
for each v∈adj[u] do
begin
tmp:=d[v];
relax(u,v);
if (tmp<>d[v]) and (not v in Q) then
enqueue(Q,v);
end;
end;
End;
4.我代码能力渣，SPFA算法有两个优化算法 SLF 和 LLL： SLF,不会。
Autor:ray007great
*/
/*
构图有2种,邻接矩阵版.最裸的最短路，对应hdu 2544
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#define N 150
#define inf 999999
using namespace std;
queue<
int>
q;
int n;
int vis[N],dis[N],map[N][N];
int spfa()
{
int i;
memset(vis,0,
sizeof(vis));
for(i=
0;i<=n;i++
)
dis[i]=
inf;
q.push(1);
vis[1]=
1;
dis[1]=
0;
while(!
q.empty())
{
int cur=
q.front();
q.pop();
for(i=
1;i<=n;i++
)
{
if(map[cur][i]!=
inf)
{
if(dis[i]>dis[cur]+
map[cur][i])
{
dis[i]=dis[cur]+
map[cur][i];
//pre[i]=cur;
if(!
vis[i])
{
vis[i]=
1;
q.push(i);
}
}
}
}
vis[cur]=
0;
}
return dis[n];
}
int main()
{
int i,a,b,c,j,m;
while(scanf(
"%d%d",&n,&m)!=EOF &&n&&
m)
{
for(i=
0;i<=n;i++
)
for(j=
0;j<=n;j++
)
map[i][j]=
inf;
for(i=
1;i<=m;i++
)
{
scanf("%d%d%d",&a,&b,&
c);
if(map[a][b]>
c)
map[a][b]=map[b][a]=
c;
}
int max=
spfa();
printf("%d\n",max);
}
return 0;
}
/*
邻接矩阵版。附：邻接矩阵不用考虑重边。
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#define N 150
#define inf 999999
using namespace std;
struct node
{
int from,to,value;
};
queue<
int>
q;
vector<node>
g[N];
int n;
int vis[N],dis[N];
int spfa()
{
int i;
memset(vis,0,
sizeof(vis));
for(i=
0;i<=n;i++
)
dis[i]=
inf;
q.push(1);
vis[1]=
1;
dis[1]=
0;
while(!
q.empty())
{
int cur=
q.front();
q.pop();
for(i=
0;i<g[cur].size();i++
)
{
int k=
g[cur][i].to;
if(dis[k]>dis[cur]+
g[cur][i].value)
{
dis[k]=dis[cur]+
g[cur][i].value;
if(!
vis[k])
{
vis[k]=
1;
q.push(k);
}
}
}
vis[cur]=
0;
}
return dis[n];
}
int main()
{
int i,a,b,c,j,m;
while(scanf(
"%d%d",&n,&m)!=EOF &&n&&
m)
{
for(i=
0;i<N;i++
) g[i].clear();
for(i=
1;i<=m;i++
)
{
scanf("%d%d%d",&a,&b,&
c);
node e;
e.from=
a;
e.to=
b;
e.value=
c;
g[e.from].push_back(e);
e.from=
b;
e.to=
a;
g[e.from].push_back(e);
}
int max=
spfa();
printf("%d\n",max);
}
return 0;
}
转载于:https://www.cnblogs.com/ray007great/archive/2013/04/26/3043863.html
相关资源：IOI国家集训队论文集1999-2019
