给你一个无向图，然后给了一个起点s和终点e，然后问从s到e的最短路是多少，中途有一个限制，那就是必须走k条边，路径可以反复走。
思路：
感觉很赞的一个题目，据说证明是什么国家队集训队论文什么的，自己没去看那个论文，就说下我自己的理解吧，对于这个题目，我们首先分析下Floyd,那个算法的过程中是在更新的dis[i][j]上再更新，再更新。。。，是想一下，我们每次都把更新的结果存下来，就是每次答案数组初始化全是INF，然后用当前的dis数组和原始的map来更新，那么更新得到的就应该是dis的状态下在多走一条边到达各个点的最短，就这样，想得到第几条边的最短路就更新几次就行了，只要结构如下
now初始化INF
for(int k = 1 ;k <= n ;k ++)for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= n ;j ++)
now[i][j] = min(now[i][j] ,dis[i][k] + map[k][j]);
dis是上一步的now，map是原始的图，有点dp的意思，如果不理解可以这样写
now初始化INF
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= n ;j ++)
for(int k = 1 ;k <= n ;k ++)
now[i][j] = min(now[i][j] ,dis[i][k] + map[k][j]);
这样就方便理解了，就是在原来的基础上在多加（强制）一条边去更新，不要感觉说Floyd的三重for循环不能调换这里面就不能调换，其实这里面的根本不是Floyd我们要的只是在加一条边更新所有，所以怎么写都行，然后就是这个题目的另一个关键，如果直接就写估计会超时，这是我们可以用类似矩阵快速幂的方式去优化，如果用到快速幂就要证明a^b = a^2(b/2)这个地方我不能说太多，因为怕说错了，我只是感觉因为这个题目的过程满足结合律，所以满足上面的那个式子，具体的就看下面代码吧。
#include<stdio.h>
#include<string.h>
#define N 220
#define INF 1000000000
typedef struct
{
int mat[N][N];
}A;
int mark[1100];
int minn(int x, int y)
{
return x < y ? x : y;
}
A Floyd (A a ,A b ,int n)
{
A c;
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= n ;j ++)
c.mat[i][j] = INF;//这个地方看好了，是初始化成INF，不是平时的Floyd直接就在更新的数组上在更新。
for(int k = 1 ;k <= n ;k ++)
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= n ;j ++)
//for(int k = 1 ;k <= n ;k ++)
c.mat[i][j] = minn(c.mat[i][j] ,a.mat[i][k] + b.mat[k][j]);
return c;
}
A Qpow_Mat(A a ,int b ,int n)
{
A c;
int mk = 0;
while(b)
{
if(b & 1)
{
!mk ? c = a : c = Floyd(c ,a ,n);
mk = 1;
}
b >>= 1;
a = Floyd(a ,a ,n);
}
return c;
}
int main ()
{
int n ,t ,s ,e ,i ,j ,a ,b ,c ,nowid;
A Ans;
scanf("%d %d %d %d" ,&n ,&t ,&s ,&e);
{
memset(Ans.mat ,255 ,sizeof(Ans.mat));
memset(mark ,0 ,sizeof(mark)) ,nowid = 0;
for(i = 1 ;i <= t ;i ++)
{
scanf("%d %d %d" ,&c ,&a ,&b);
if(!mark[a]) mark[a] = ++nowid;
if(!mark[b]) mark[b] = ++nowid;
a = mark[a] ,b = mark[b];
Ans.mat[a][b] = Ans.mat[b][a] = c;
}
for(i = 1 ;i <= nowid ;i ++)
for(j = 1 ;j <= nowid ;j ++)
if(Ans.mat[i][j] == -1) Ans.mat[i][j] = INF;
Ans = Qpow_Mat(Ans ,n ,nowid);
printf("%d
" ,Ans.mat[mark[s]][mark[e]]);
}
return 0;
}