倍增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)


相关推荐

  • CAN协议深度解析-简单易懂协议详解[通俗易懂]

    CAN协议深度解析-简单易懂协议详解[通俗易懂]CAN-bus通信帧共分为数据帧、远程帧、错误帧、过载帧和帧间隔五种类型。显形隐形电平CAN-bus发布了ISO11898和ISO11519两个通信标准,此两个标准中差分电平的特性不相同。显性电平:总线上只要有1个节点驱动为显性,则总线表现为显性位电平,逻辑解析为“0”。隐形电平:只有总线上的各节点都不将总线驱动成显性电平,总线才表现为隐形位对应的电平,逻辑解析为“1”。位填充:位填充是为防止突发错误而设定的功能。当同样的电平持续5位时,则添加一个位的反型数据。数据帧数据帧结构上

  • 【matlab】函数meshgrid的用法详解(生成网格矩阵)和ndgrid的区别及用法「建议收藏」

    【matlab】函数meshgrid的用法详解(生成网格矩阵)和ndgrid的区别及用法「建议收藏」meshgrid函数用来生成网格矩阵,可以是二维网格矩阵,也可以是三维。对于生成二维网格,用法为:[xy]=meshgrid(ab); %a和b是一维数组,如a=[123];b=[234];则生成的x和y都是二维的矩阵,x的每行都是123,共三行,y每列都是234,共三列。举个实例:Forexample, toevaluateth

  • 面试JAVA常被问到的问题(持续更新中)

    面试JAVA常被问到的问题(持续更新中)引言有的面试会被问到有没有写博客,这时候我尴尬,不知道怎么回答,所以这篇文章仅仅是把我面试JAVA的遇到的问题记录下来而已,也算是我写博客迈出的第一步,起码,以后被问到:有没有写博客?我可以回答,我写过。 (最主要的是以后换工作我不用频繁百度常见面试题了。。。。)ps1,别把我太当回事,我是个LJ;2,说得不对的地方请多多包涵,想看更详细的请百度官方文档和其他大佬的文章;3,如果有被问到…

  • hdu 2058_HAL248

    hdu 2058_HAL248ThesumproblemTimeLimit:5000/1000MS(Java/Others)  MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):24299  AcceptedSubmission(s):7247ProblemDescriptionGivenas

  • 论坛的后缀_discuz!q

    论坛的后缀_discuz!q第一步:去掉论坛模板路径(这里以默认模板为例)/template/default/common找到header_common.htm这个文件下载$navtitle–$_G[‘setting’][‘bbname’]-PoweredbyDiscuz!$_G[‘setting’][‘seohead’]

发表回复

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

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