大家好,又见面了,我是你们的朋友全栈君。
有这样的一道题:
给定一张图,求其中恰好经过 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;
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/127096.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...