本文主要是介绍[POJ3613]Cow Relays Floyd倍增，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
怎么说呢 如果有看论文（矩阵乘法-俞华程） 这道题还是相当异常非常的简单 （除了本人自己玩自己忘记离散化 直接函数爆栈调N久甚至求助吴老师之外）
唯一需要注意的就是单位矩阵的建立是对角线为0 其他全部为正无穷
Floyd倍增的原因论文上有说 其实我也没怎么看
废话就说到这里 上代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN 100
#define MAXM 100
#define INF 0x3f3f3f3f
typedef int LL;
struct Matrix{ int n, m; LL A[MAXN+10][MAXN+10];
}E, Z, A;
int Map[MAXN+10][MAXN+10];
int n, m, ST, ED, K, Fish;
int ID[MAXN*10+10], idcnt;
int N;
void Get_E()
{memset(E.A, 0x3f, sizeof(E.A));for(int i = 0; i < MAXN; i++) E.A[i][i] = 0;
}
void New_mul(Matrix AA, Matrix BB, Matrix &Ans)
{Matrix D;memset(Ans.A, 0x3f, sizeof(D.A));Ans.n = D.n = AA.n;Ans.m = D.m = BB.m;for(int k = 0; k < MAXN; k++) for(int i = 0; i < MAXN; i++) for(int j = 0; j < MAXN; j++) if(Ans.A[i][j] > AA.A[i][k] + BB.A[k][j]) Ans.A[i][j] = AA.A[i][k] + BB.A[k][j];
}
void pow_mod(Matrix A, int k, Matrix &Ans)
{Matrix ans = E, t = A, tmp;Ans.n = ans.n = A.n;Ans.m = ans.m = A.m;while(k){if(k & 1){New_mul(ans, t, tmp);ans = tmp;}New_mul(t, t, tmp);t = tmp;k >>= 1;}memcpy(Ans.A, ans.A, sizeof(ans.A));
}
Matrix Ans;
int main()
{ios::sync_with_stdio(false);Get_E();memset(Map, 0x3f, sizeof(Map));cin >> n >> m >> ST >> ED;ST--; ED--;memset(ID, -1, sizeof(ID));for(int i = 0; i < m; i++){int u, v, d;cin >> d >> u >> v;u--;v--;if(~ID[u] == 0) ID[u] = idcnt++;if(~ID[v] == 0) ID[v] = idcnt++;Map[ID[u]][ID[v]] = Map[ID[v]][ID[u]] = d;}E.n = E.m = Z.n = Z.m = A.n = A.m = MAXN;memcpy(A.A, Map, sizeof(Map));pow_mod(A, n, Ans);cout << Ans.A[ID[ST]][ID[ED]] << '\n';
}这篇关于[POJ3613]Cow Relays Floyd倍增的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
