前言

这道题正向思考是比较难以想出来的，蕴含了一类解题的思路，同时也可以当作一类板子题记忆。

题面

Link

给定一个有向图，求 \(s\) 到 \(t\) 的最短路径。特殊点在于，对于一条路径， 如果经过的边数小于等于 \(k\)，那么该路径总长度为构成该路径的所有边的长度之和；否则为该路径上最长的 \(k\) 条边的长度之和。

解法

步骤

设答案为 \(ans\)，我们先将 \(ans\) 赋值为原图的最短路。然后依次枚举每条边的长度 \(w_x\)，对于每个 \(w_x\)，我们将原图上每条边的长度 \(w_i\) 都减去 \(w_x\)，如果减去后为负数就设为 \(0\)，即 \(w_i=\max\{w_i-w_x,0\}\)，求出此时的最短路，加上 \(k\times w_x\) 后更新 \(ans\)。

正确性证明

最优路径总边数大于 \(k\) 的情况

假设已经知道了最优解，\(w_x\) 取 \(w_{最优}\) 时生成的图的最短路径上留下的边（我们称边长非零的边为留下的边）的数量一定刚好为 \(k\)，最短路径上其他的边边长为 \(0\)。此时最短路径长度为 \(\Large\sum\limits_{E_i\in留下的边}\normalsize (E_i原边长-w_x)\)，再加上 \(k\times w_x\) 后刚好等于原图这 \(k\) 条边长度之和。

可以发现对于每次枚举到的 \(w_x\)，计算出的解都不会更优于最优解，可以类似理解为答案是具有凸性的：

• 当 \(w_x < w_{最优}\) 时，由于每条边都相对变长了，显然此时最短路径只会变长不会变短。对于最短路径原先的 \(k\) 条边，它们加上 \(k\times w_x\) 后变回原边长；但此时的最短路径相比最优解最短路径可能还多出来一些非零边，因此此时的答案一定是大于等于最优解最短路径长度的。
• 当 \(w_x > w_{最优}\) 时，令此时最短路径上留下的边为 \(k'\)，由于边权减去的变多了，那么肯定 \(k' < k\)，假如说我们仍强行按照最优解的那 \(k\) 条边统计答案，并且让多出来的 \((k-k')\) 条边保留负数而不变为 \(0\)，此时 \(\Large\sum\limits_{E_i\in最优解的k条边}\normalsize (E_i原边长-w_x) + k\times w_x\) 应该是等于最优解长度的，问题是实际上式子为 \(\Large\sum\limits_{E_i\in最优解的k条边}\normalsize \max\{(E_i原边长-w_x),0\} + k\times w_x\)，即不会保留负数，此时统计出的答案将会大于最优解。如果还是没懂可以试着自己手推几个例子，简明扼要的理解就是由于“减去后若是负数就强制设为 \(0\)，减的变少了，但加回来的还是一样”导致了答案反而变大。

另外，为什么只需要枚举每条边的长度，而不是枚举所有长度（\(1,2,3,\dots,MAXN)\)？

假设有两条边的长度分别为 \(w_1\)​ 和 \(w_2\)​（\(w_1 < w_2\)​），可以发现如果枚举 \(w_x\in (w_1,w_2)\)​，边权变为 \(0\)​ 的边与 \(w_x=w_1\)​ 时一致，并且与上文 \(w_x > w_{最优}\)​ 同理，答案只会相等或者更劣。因此没必要考虑两条边长之间的长度，最优的 \(w_x\)​​ 一定是某一条边的边长，解具有离散性。

因此这样一定会枚举到最优解。

最优路径总边数小于等于 \(k\)​ 的情况

这种情况说明原图的最短路即为总边数小于等于 \(k\) 的最短路，因此在最开始就用原图最短路更新 \(ans\)。

代码

#include<bits/stdc++.h>
using namespace std;
template<class T>inline void rd(T &x){
    T res=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1; ch=getchar();}
    while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
    x=res*f;
}
template<class T>inline void wt(T x){
    if(x<0){x=-x;putchar('-');}
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
typedef long long LL;
typedef pair<LL,int> pli;
const int MAXN=1005,MAXM=2005;
int n,m,k,s,t,ecnt=0,head[MAXN];
LL ans;
struct EDGE{
    int v,w,nxt;
}e[MAXM];
inline void add(int u,int v,int w){
    e[++ecnt].v=v;
    e[ecnt].w=w;
    e[ecnt].nxt=head[u];
    head[u]=ecnt;
}
vector<int>price;
inline LL dijkstra(const int &val){
    static bitset<MAXN>vis;
    static LL dis[MAXN];
    priority_queue<pli,vector<pli>,greater<pli> >pq;
    vis.reset();memset(dis,0x3f,sizeof(dis));
    dis[s]=0;pq.push(make_pair(0,s));
    while(!pq.empty()){
        int u=pq.top().second,v;pq.pop();
        LL w;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt){
            v=e[i].v;
            w=max(e[i].w-val,0);
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                pq.push(make_pair(dis[v],v));
            }
        }
    }
    return dis[t];
}
int main(){
    rd(n);rd(m);rd(k);rd(s);rd(t);
    for(int i=1,x,y,z;i<=m;i++){
        rd(x);rd(y);rd(z);
        add(x,y,z);
        price.push_back(z);
    }
    sort(price.begin(),price.end());
    unique(price.begin(),price.end());
    ans=dijkstra(0);
    for(auto it:price){
        ans=min(ans,dijkstra(it)+1LL*k*it);
    }
    wt(ans);
    return 0;
}

总结

这种题的特征是答案具有凸性，含有“恰好 \(k\) 个”类似的描述，并且答案是离散的可以枚举，即可以尝试用本文提到的思路作答。

另外，这种做法与wqs二分有思想上的类似之处，可以互相参考。