本文主要是介绍POJ 3613 Cow Relays floyd+快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>using namespace std;int N,T,S,E,num;
map<int,int> mp;struct Matrix{int ma[210][210];void clear(){memset(ma,0x3f,sizeof(ma)); //初始化一定要大，否则WA}
};Matrix Floyd(Matrix a,Matrix b){Matrix dis;dis.clear();int i,j,k;for(k=1;k<=num;k++) //一次floyd 是找到一个中间点for(i=1;i<=num;i++)for(j=1;j<=num;j++)if(dis.ma[i][j]>a.ma[i][k]+b.ma[k][j])dis.ma[i][j]=a.ma[i][k]+b.ma[k][j];return dis;
}Matrix Solve(Matrix a,int k){Matrix ans=a;while(k){if(k&1){ans=Floyd(ans,a);}a=Floyd(a,a);k>>=1;}return ans;
}int main(){//freopen("input.txt","r",stdin);Matrix a;while(~scanf("%d%d%d%d",&N,&T,&S,&E)){num=0;mp.clear();a.clear();int u,v,w;while(T--){scanf("%d%d%d",&w,&u,&v);if(mp[u]==0)mp[u]=++num;if(mp[v]==0)mp[v]=++num;if(a.ma[mp[u]][mp[v]]>w)a.ma[mp[u]][mp[v]]=a.ma[mp[v]][mp[u]]=w;} a=Solve(a,N-1); // N 条边 ，经过 N-1 个点 printf("%d\n",a.ma[mp[S]][mp[E]]);}return 0;
}我们知道线性代数中有： 在只 含有 01邻接矩阵 A的 K次 方 C=A^K， C[i][j]表示 i点到 j点正好经过 K条边的路径数。
而floyd则是每次使用一个中间点k去更新i,j之间的距离，那么更新成功表示i,j之间恰有一个点k时的最短路，如果做N - 1次floyd那么不就是i,j之间借助N - 1 个点时的最短路了
当 c[i][j] > a[i][k] + a[k][j] 则更新
第二次将c[i][j]拷贝回到a[i][j]当中，并将c[i][j]重新置为INF，再做一次，则是在原来的基础上在i,j之间再用一个点k来松弛，这时候i,j之间实际上已经是两个点了，
但是这个题的 n （边数太大）我们要用到 倍增法，其实即使 二分思想 例如 经过 5 条边 把 （4 个点） == 两个 2 条边的 松驰一次 ；
这篇关于POJ 3613 Cow Relays floyd+快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
