具体见：SPFA，这里面讲的很详细。它的大致算法流程：
①、初始化时，把源点pos加入到队列中，并置Dist[pos]=0,其它各点到源点的距离设为Dist[V]为∞；
②、每次取出队列中的一个元素，并以该点为中间点，对于该点有边相连的点V进行松弛操作，如果松弛操作成功，改进Dist[v]的值，并把v加入到队列中；
③、反复进行②操作，直到队列为空，Dist[v]表示源点到其它各点的最短距离。
题1：Tyvj 1423(拉绳子)，枚举每个点到其它顶点的最短路径，取出最长的路径就是能拉紧环的最大的个数。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=110;
const int M=10010;
const int Inf=10000010;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int n,m,visit[N],Dist[N];
struct ArcNode
{ void Add(int u,int v)
{ next[num]=Prior[u];
Len[num]=1; //保存权值
data[num]=v;
Prior[u]=num++;
}
void Init()
{ CLR(Prior,-1);
num=0;
}
int Prior[N],next[M],data[M],Len[M],num;
}A;
void SPFA(int s)
{ int u,v,w;
fill(Dist,Dist+N,Inf);//Dist保存的是源点s到其它顶点的最短路径
CLR(visit,0);
Dist[s]=0;
queue<int> Q;
Q.push(s);
visit[s]=1;
while(!Q.empty())
{ u=Q.front();
Q.pop();
visit[u]=0;
for(int i=A.Prior[u];i!=-1;i=A.next[i])
{ w=A.Len[i];
v=A.data[i];
if(Dist[u]+w<Dist[v])
{ Dist[v]=Dist[u]+w;
if(!visit[v])
{ Q.push(v);
visit[v]=1;
}
}
}
}
}
int main()
{ int u,v;
scanf("%d%d",&n,&m);
A.Init();
for(int i=0;i<m;i++)
{ scanf("%d%d",&u,&v);
A.Add(u,v);
A.Add(v,u);
}
int max=0;
for(int i=1;i<=n;i++)
{ SPFA(i);
for(int j=1;j<=n;j++)
if(max<Dist[j]) max=Dist[j];
}
printf("%d\n",max);
return 0;
}
题2：Tyvj 1232(跳格子)，比较的简单，关键是构图，对于任意顶点看与它相邻的那个点的符号是否相同，不同，则把之间的权值定为2，否则定为1，然后转化为了源点到终点的最短路径。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=510;
const int M=2000010;
const int Inf=10000010;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int n,m,visit[N*N],Dist[N*N];
char map[N][N];
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
struct ArcNode
{ void Add(int u,int v,int w)
{ next[num]=Prior[u];
Len[num]=w; //保存权值
data[num]=v;
Prior[u]=num++;
}
void Init()
{ CLR(Prior,-1);
num=0;
}
int Prior[N*N],next[M],data[M],Len[M],num;
}A;
bool Inside(int x,int y)
{ return x>=0&&x<n&&y>=0&&y<m;
}
void SPFA(int s)
{ int u,v,w;
fill(Dist,Dist+N*N,Inf);
CLR(visit,0);
Dist[s]=0;
queue<int> Q;
Q.push(s);
visit[s]=1;
while(!Q.empty())
{ u=Q.front();
Q.pop();
visit[u]=1;
for(int i=A.Prior[u];i!=-1;i=A.next[i])
{ w=A.Len[i];
v=A.data[i];
if(Dist[u]+w<Dist[v])
{ Dist[v]=Dist[u]+w;
if(!visit[v])
{ Q.push(v);
visit[v]=1;
}
}
}
}
}
int main()
{ int u,v,w,sx,sy,ex,ey;
scanf("%d%d",&n,&m);
A.Init();
getchar();
for(int i=0;i<n;i++)
scanf("%s",map[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
for(int k=0;k<4;k++)
{ u=i+dx[k];
v=j+dy[k];
if(Inside(u,v))
{ w=1;
if(map[u][v]!=map[i][j]) w=2;
A.Add(i*m+j,u*m+v,w); //构图
A.Add(u*m+v,i*m+j,w);
}
}
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
SPFA((sx-1)*m+(sy-1));
printf("%d\n",Dist[(ex-1)*m+ey-1]);
return 0;
}
题3：Tyvj 1238(路径)，个人觉得是比较经典的一题了，这个题的大概意思是求0到1的最小费用的最短路径，也就是在要保证0到1的边最少的情况下费用尽可能最少，由于要边数最少，我们可以在每条边的权值上加一个很大的数，我加的是100000，然后再用SPFA求最短路。最后的路径%100000即可，(你将任意边的权值+100000后，每多加一条边就相当与多加了100000的费用，相比下来所以查询的时候自然而然的就选择了边数最小的路径来降低费用)。注意不要加太大，当心爆掉~~~
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=110;
const int M=1010;
const int Inf=1000010;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int n,m,visit[N*N],Dist[N*N];
struct ArcNode
{ void Add(int u,int v,int w)
{ next[num]=Prior[u];
Len[num]=w; //保存权值
data[num]=v;
Prior[u]=num++;
}
void Init()
{ CLR(Prior,-1);
num=0;
}
int Prior[N*N],next[M],data[M],Len[M],num;
}A;
bool Inside(int x,int y)
{ return x>=0&&x<n&&y>=0&&y<n;
}
void SPFA(int s)
{ int u,v,w;
fill(Dist,Dist+N*N,Inf);
CLR(visit,0);
Dist[s]=0;
queue<int> Q;
Q.push(s);
visit[s]=1;
while(!Q.empty())
{ u=Q.front();
Q.pop();
visit[u]=1;
for(int i=A.Prior[u];i!=-1;i=A.next[i])
{ w=A.Len[i];
v=A.data[i];
if(Dist[u]+w<Dist[v])
{ Dist[v]=Dist[u]+w;
if(!visit[v])
{ Q.push(v);
visit[v]=1;
}
}
}
}
}
int main()
{ int u,v,w;
scanf("%d%d",&n,&m);
A.Init();
getchar();
for(int i=0;i<m;i++)
{ scanf("%d%d%d",&u,&v,&w);
w+=100000;
A.Add(u,v,w);
}
SPFA(0);
printf("%d\n",Dist[1]%100000);
return 0;
}