大家好，又见面了，我是你们的朋友全栈君。
有这样的一道题：
给定一张图，求其中恰好经过 m 条边的路径的长度最小值。
(n<=200,m<=109)
对于这种题型，可以使用倍增Floyd求解。
由于Floyd算法的奇特性质：每次加入一个点进行更新。如果我们把它改写为：
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++)
check(d[i][j],d[i][k]+d[k][j]);那么这得到的就是经过两条边的最短距离的，同样的，我们就可以将这个拓展为倍增，就可以解决这个问题了。附上部分代码。
（黄学长的代码写的真飘逸，学习了）
struct Floyd{
int d[N][N];
Floyd(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=INF;
}
Floyd operator *(const Floyd &a)const{
Floyd res;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
check(res.d[i][j],d[i][k]+a.d[k][j]);
return res;
}
}ans,A;
void solve(){
Init();//A设为原图
while(m){
if(m&1)ans=ans*A;
A=A*A;
m>>=1;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/127096.html原文链接：https://javaforall.net
