[Acwing] 通信线路 二分|DP + 最短路

前言

简直不是一般的难！！！ 传送门 :

题目分析

路径代价 每一条路径上 最大的边是 这条路的代价

对于k 可以让路径免费,只不过是多加了一条 为0 的重边

最后题目转换为 :

我们可以设置 k k k条边权为 0 0 0的边,让我们求从 1 1 1到 n n n的最小花费

令 f [ x , p ] f[x,p] f[x,p] 表示从 1号节点 到x号节点,途中经过 p 条权值为0的边

因此

• 如果新加入的边是非零边 我们就有公式 f [ y , p ] = m a x ( f [ x ] [ p ] , z ) f[y,p] = max(f[x][p],z) f[y,p]=max(f[x][p],z)

• 如果加入的是零边 f [ y ] [ p + 1 ] = d [ x ] [ p ] f[y][p+1] = d[x][p] f[y][p+1]=d[x][p]

因此对于答案 我们只需要枚举所有的 k即可

CODE

///d[x,p] 表示从 1号节点 到 x 号节点 途径 p条权值0的边


#include 
using namespace std;
const int N = 4e3+10,M =4e4+10;
int h[N],e[M],ne[M],w[M],idx;
int n,m,k;
int f[N][N];
int st[N];

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}

void spfa(int s )
{
    memset(f,0x3f,sizeof f);
    f[s][0] = 0;
    ///从1 到 s 号节点 途0条边权为0的边
    st[s] = 1;
    queue q;
    q.push(s);

    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = 0 ;
        for(int i= h[t];~i;i=ne[i])
        {
            int j = e[i];
            int z = w[i];
            int w = max(f[t][0],z);

            if(f[j][0] >w)
            {
                f[j][0] = w;
                if(!st[j])
                {
                    q.push(j),st[j] = 1;
                }
            }

            for(int p=1;pw)
                {
                    f[j][p] = w;
                    if(!st[j])
                    {
                        q.push(j);
                        st[j] = 1;

                    }
                }
            }


        }
    }
}
void solve()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);

    for(int i=1; i>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    spfa(1);
    int ans = 1e9;
    for(int i=0;i