倍增Floyd「建议收藏」

全栈程序员站长

发布于 2022-07-25 09:23:56

2270

发布于 2022-07-25 09:23:56

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

有这样的一道题：

给定一张图，求其中恰好经过 m m条边的路径的长度最小值。 (n<=200,m<=109) (n<=200,m<=10^9)

对于这种题型，可以使用倍增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.cn/127096.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年4月9，如有侵权请联系 cloudcommunity@tencent.com 删除

https