Java教程

分层图跑最短路:适用于可以对一定数量的前k条边权可以免费 减半的时候 omk的空间

本文主要是介绍分层图跑最短路:适用于可以对一定数量的前k条边权可以免费 减半的时候 omk的空间,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

下层到上层的边不用建 从上层到下层就已经代表了做了一次选择 如果还能回到上层的话会出问题的
因为可以免费 k 次,所以我们要建 k+1 层图
在 k+1 层图上我们已经不能再往下了,即免费操作已用完

    for(int i=1,x,y,z;i<=p;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);    //本层建边
        for(int j=1,z1=0;j<=k;j++)//z1是前k条边可以跑的边权
        {
            add(x+(j-1)*n,y+j*n,z1);    //第j层和第j+1层间的建边 第j层的y到第j层的y+1
            add(y+(j-1)*n,x+j*n,z1);//第j层x 到 第j+1层的y
            add(x+j*n,y+j*n,z);
            add(y+j*n,x+j*n,z);    //第j+1层建边
        }
    }
    //求答案法一 每一层的终点向下一层的终点连边保证第k层的终点就是答案
    for(int i=1,z=0;i<=k;i++)
        add(i*n,(i+1)*n,z);//防止可以免费的边大于1-n的路径这种情况 这样保证
    res = dis[(k+1)*n];

    //求答案法二 的时候 第一层到第k+1层
    for(int i=0,i<=k,i++){
        an=min(an,dis[t+i*n]);//k次操作内的最短路
    }

求第k+1条贵的长度https://www.acwing.com/problem/content/description/342/

现在我们要这么更新:
z=max(edge,dis[x]); //edge是当前边权值
if ( dis[y] > z ) dis[y] = z;


                    
这篇关于分层图跑最短路:适用于可以对一定数量的前k条边权可以免费 减半的时候 omk的空间的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!