倍增Floyd「建议收藏」

倍增Floyd有这样的一道题:给定一张图,求其中恰好经过mm条边的路径的长度最小值。(n<=200,m<=109)(n<=200,m<=10^9)对于这种题型,可以使用倍增Floyd求解。由于Floyd算法的奇特性质:每次加入一个点进行更新。如果我们把它改写为:for(inti=0;i<=n;i++)for(intj=0;j<=n;j++)for(intk=

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

有这样的一道题:

给定一张图,求其中恰好经过 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账号...

(0)


相关推荐

  • python入门教程(非常详细)书_python编程入门基础

    python入门教程(非常详细)书_python编程入门基础【Python第1课】安装…6【Python第2课】print.7【Python第3课】IDE.10【Python第4课】输入…12【Python第5课】变量…14【Python第6课】bool.16【Python第7课】if.19【Python第8课】while.23【Python第9课】random.

    2022年10月12日
  • 远程连接oracle01017,sqlplus远程sys用户登录ora 01017的解决方法[通俗易懂]

    远程连接oracle01017,sqlplus远程sys用户登录ora 01017的解决方法[通俗易懂]UsingORAPWDWhenyouinvokethispasswordfilecreationutilitywithoutsupplyinganyparameters,youreceiveamessageindicatingtheproperuseofthecommandasshowninthefollowingsampleoutput…

  • swift 中protocol(协议)中的可选(optional)方法

    swift 中protocol(协议)中的可选(optional)方法

  • pycharm 中切换虚拟环境的总结

    pycharm 中切换虚拟环境的总结一、理清思路太重要了1、首先了解对应虚拟环境的运行机制你才能找到正确的解决方案2、分享我个人遇到的问题及解决方案首先安装好了django框架后,在cmd里面能正常运行,但是在Pycharm里面总是不能运行成功,老是报没有激活的问题。首先我们来看在cmd中成功运行的界面:在cmd里面我们切换至对应工程的路径输入命令:pythonmanage.pyrunserver127.0.0.1:8888,我们可以看到Startingdevelopmentserverathttp://127.0

  • python3.6实现的A星算法

    python3.6实现的A星算法A星算法原理:原理我就不再赘述,可以参考这篇博客https://blog.csdn.net/hitwhylz/article/details/23089415最近用js写了一遍,用的同样的算法,需要js代码的看这里:https://blog.csdn.net/qq_39687901/article/details/85697127代码实现:首先添加两个通用类…

  • java ac自动机_ac自动机java版

    【实例简介】从别的共享资源下载的java版ac自动机,已验证使用非常好。【实例截图】【核心代码】ahocorasick_java-1.1└──ahocorasick_java-1.1├──ahocorasick│├──pom.xml│├──src││└──main││└──java││└──org││…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号