本文主要是介绍POJ 3613 Cow Relays floyd + 快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本题的大意就是问从S 到 T 经过边得个数恰为k的最短路是多少。
参考国家队集训论文 08年的 矩阵乘法在信息学中的应用
01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数
对应于这道题,对邻接图进行K次floyd之后,C[i][j]就是点i到j正好经过K条边的最短路
但是K次floyd难免复杂度太高了。 所以可以使用快速幂的方法，二分的往上求解
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#define MAXN 1005
#define MAXM 500005
#define INF 1000000000
using namespace std;
int k, m, s, t;
int ans[MAXN][MAXN], mp[MAXN][MAXN], tmp[MAXN][MAXN], dis[MAXN][MAXN];
int used[MAXN], v[MAXN], num;
void floyd(int c[][MAXN], int a[][MAXN], int b[][MAXN])
{for(int k = 0; k < num; k++)for(int i = 0; i < num; i++)for(int j = 0; j < num; j++)if(c[v[i]][v[j]] > a[v[i]][v[k]] + b[v[k]][v[j]])c[v[i]][v[j]] = a[v[i]][v[k]] + b[v[k]][v[j]];
}
void copy(int a[][MAXN], int b[][MAXN])
{for(int i = 0; i < num; i++)for(int j = 0; j < num; j++){a[v[i]][v[j]] = b[v[i]][v[j]];b[v[i]][v[j]] = INF;}
}
void slove(int k)
{while(k){if(k & 1){floyd(dis, ans, mp);copy(ans, dis);}floyd(tmp, mp, mp);copy(mp, tmp);k >>= 1;}
}
int main()
{int x, y, w;scanf("%d%d%d%d", &k, &m, &s, &t);for(int i = 0; i <= 1000; i++){for(int j = 0; j <= 1000; j++){mp[i][j] = INF;tmp[i][j] = INF;dis[i][j] = INF;ans[i][j] = INF;}ans[i][i] = 0;}num = 0;for(int i = 0; i < m; i++){scanf("%d%d%d", &w, &x, &y);if(!used[x]){used[x] = 1;v[num++] = x;}if(!used[y]){used[y] = 1;v[num++] = y;}if(mp[x][y] > w)mp[x][y] = mp[y][x] = w;}slove(k);printf("%d\n", ans[s][t]);return 0;
}
这篇关于POJ 3613 Cow Relays floyd + 快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
