POJ 3613 快速幂+Floyd变形（求限制k条路径的最短路）

题意：
      给你一个无向图，然后给了一个起点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 1000000000typedef 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\n" ,Ans.mat[mark[s]][mark[e]]);}return 0; }

总结

以上是生活随笔为你收集整理的POJ 3613 快速幂+Floyd变形（求限制k条路径的最短路）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。