P6961 [NEERC2017]Journey from Petersburg to Moscow

· · 题解

分析：

前排先 stO 一下题面里的 \color{black}{K}\color{red}{arry5307}

对于这个题来说，我们发现没有办法直接找到每条路径第 k 大的边是谁，所以我们考虑直接钦定每一条边是第 k 大的情况

假设我们钦定一条边权为 w 的边为第 k 大的边，那么所有小于 w 的边边权变为 0 ,大于等于 w 的边权变为 x-w ，这样跑完最短路后的代价就是 ans=dis_n+k*w

但是我们发现，这样做的话可能存在三种情况

  2. 证明：因为这种情况下，我们得到的答案等价于将第 $1$ 大到第 $k'$ 大边的边权不变，但第 $k'+1$ 到第 $k$ 大的边的边权变大为 $w$ ,所以答案偏大
  3. w$ 为此时最短路上大于第 $k'\ (k'>k)$ 大的边，那么我们求得的答案还是大于实际情况的，因为有一些原本该变成 $0$ 的边没有变成 $0

由此看来我们枚举边得到的答案是不小于实际答案的，那么我们只需要钦定每一条边，然后对所有的答案取最小值那么一定会得到恰好第 k 大的情况，复杂度 O(m^2\log )

tip：

可能存在一种情况就是不钦定任何边的情况下，原图的最短路小于 k 条边，那么这种情况直接是最优解，因为至少需要付前 k 条边的费用，所以最后的答案还要和这种情况也取一下 \min

代码：

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define pll pair<long long,long long>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second

using namespace std;

namespace zzc
{
    typedef long long ll;
    inl ll read()
    {
        ll x=0,f=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
        while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
        return x*f;
    }

    const ll maxn = 3005;
    const ll inf = 0x3f3f3f3f3f3f3f3f;
    ll n,m,k,cnt,ans;
    ll head[maxn],dis[maxn];
    bool vis[maxn];
    priority_queue<pll> q;

    struct edge
    {
        ll to,nxt,w;
    }e[maxn<<1];

    inl void add(ll u,ll v,ll w)
    {
        e[++cnt].to=v;
        e[cnt].w=w;
        e[cnt].nxt=head[u];
        head[u]=cnt;
    }

    inl void dijkstra(ll x)//x 表示我们钦定的第 k 大的边的边权
    {
        memset(dis,0x3f,sizeof(dis));
        memset(vis,false,sizeof(vis));
        dis[1]=0;q.push(mk(0,1));
        while(!q.empty())
        {
            ll u=q.top().sec;q.pop();
            if(vis[u]) continue;
            vis[u]=true;
            for(reg ll i=head[u];i;i=e[i].nxt)
            {
                ll v=e[i].to;
                ll w=max(0ll,e[i].w-x);//记得要和 0 取 max
                if(dis[v]>dis[u]+w)
                {
                    dis[v]=dis[u]+w;
                    q.push(mk(-dis[v],v));
                }
            }
        }

    }

    void work()
    {
        ll a,b,c;
        n=read();m=read();k=read();
        for(reg ll i=1;i<=m;i++)
        {
            a=read();b=read();c=read();
            add(a,b,c);add(b,a,c);
        }
        dijkstra(0);ans=dis[n];//tip 里提到的情况
        for(ll i=1;i<=(m<<1);i+=2)
        {
            dijkstra(e[i].w);
            ans=min(ans,dis[n]+k*e[i].w);
        }
        printf("%lld\n",ans);
    }

}

int main()
{
    zzc::work();
    return 0;
}