转载：http://www.cnblogs.com/Missa/archive/2012/09/03/2669746.html
题意：
求从一个点s 到 一点 e 经过 n 条边的最短路经是多少（可以有重边）
贴一个floyd算法讲解：
http://blog.csdn.net/niushuai666/article/details/6772706
以前一直没仔细想过floyd算法，觉得很简单，今天做这题的时候，看网上的报告都有一句：floyd是每次使用一个中间点k去更新i,j之间的距离，那么更新成功表示i,j之间恰有一个点k时的最短路，如果做N - 1次floyd那么不就是i,j之间借助N - 1 个点时的最短路了。看了很久不明白为什么。也对floyd的最外围的那个k<n产生了疑惑。后来突然想到了，floyd每次更新的都是本身，假如k=3时，dis[1][5]借助dis[1][3]和dis[3][5]成为最短路。不需要去知道1,3之间有多少个点，因为前面已经求出，，（dp?）只知道这一次求出的dis[1][5]多加了一个3这个点。
回到这题，floyd算法是对自身矩阵更新，而这道题却是更新到另一个矩阵上，所以不会出现刚更新过的值又来更新。。例如下面代码的b.mat[1][3] c.mat[3][5]就分别代表上面的dis[1][3],dis[3][5].我们不需要知道tmp.mat[1][5]已经有的点个数。（即已经更新的次数。）只知道，这次更新会加入一个3到他们中间。所以更新k-1次就行。
这个题目我们可以用一个矩阵f[i][j][n]表示进过的边数为n的i到j的最短路，利用二分的思想就可以得到f[i][j][n]=min{f[i][k][n/2]+f[k][j][n-n/2]}，这样就可以用快速幂去做了。只要先求得f[i][k][n/2]，就可以利用f[i][k][n/2]求得f[k][j][n-n/2]，于是一共只需要计算O(logn)个矩阵，每个矩阵是2维的，计算的时候可以用floyd。
void floyd(Mat b,Mat c)
{
tmp.init();
for(int k=1;k<=cnt;k++)
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
{
if(b.mat[i][k] <0 || c.mat[k][j] <0)
continue;
if(tmp.mat[i][j]<0 || tmp.mat[i][j] > b.mat[i][k] + c.mat[k][j] )
tmp.mat[i][j] = b.mat[i][k] + c.mat[k][j];
}
}
注意的地方：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 205
int n,t,st,en;
struct Mat
{
int mat[maxn][maxn];
void init()
{
memset(mat,-1,sizeof(mat));
}
};
int v[1005];//离散化用
Mat ans,tmp,map;
int cnt;//顶点个数
void init()
{
int val,s,e;
memset(v,0,sizeof(v));
cnt=0;
ans.init();
tmp.init();
map.init();
for(int i=0;i<maxn;i++)
ans.mat[i][i]=0;
for(int i=0;i<t;i++)
{
scanf("%d%d%d",&val,&s,&e);
if(v[s]==0)
{
++cnt;
v[s]=cnt;
}
if(v[e]==0)
{
++cnt;
v[e]=cnt;
}
if(map.mat[v[s]][v[e]]<0 || map.mat[v[s]][v[e]] > val)
map.mat[v[s]][v[e]]=map.mat[v[e]][v[s]]=val;
}
}
void floyd(Mat b,Mat c)
{
tmp.init();
for(int k=1;k<=cnt;k++)
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
{
if(b.mat[i][k] <0 || c.mat[k][j] <0)//意味着是inf
continue;
if(tmp.mat[i][j]<0 || tmp.mat[i][j] > b.mat[i][k] + c.mat[k][j] )
tmp.mat[i][j] = b.mat[i][k] + c.mat[k][j];
}
}
Mat copy()
{
Mat a;
for(int i=0;i<=cnt;i++)
for(int j=0;j<=cnt;j++)
a.mat[i][j]=tmp.mat[i][j];
return a;
}
void solve()
{
while(n)//虽然这里是n，像是更新了n次。但是下面80行那里第一次调用的时候其实并未更新。只是把map,传递给tmp再转给ans.
{
if(n&1)
{
floyd(ans,map);
ans=copy();
}
floyd(map,map);
map=copy();
n>>=1;
}
}
int main()
{
while(scanf("%d%d%d%d",&n,&t,&st,&en) != EOF)
{
init();
solve();
printf("%d\n",ans.mat[v[st]][v[en]]);
}
return 0;
}
1、N次floyd可以用倍增思想加速，就是自底向上的二分。类似求矩阵快速幂（M67大牛）。
2、这里还有一点要注意，T的范围是(2~100),所以最多顶点只有200，而顶点标号的范围却(1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000)。这样我们可以将编号离散化。
3、最后一点这个题的inf要开很大。开始开的是0x5fffffff还是wa了。后来看了某个博客 可以把inf定义为-1。就没这个问题了。值得学习。
ps:这道题还是有点似懂非懂.....