题解：P6961 [NEERC 2017] Journey from Petersburg to Moscow

题目链接

好像没有严谨证明的题解（可能只是我没有看到），于是我来写一个。

我们假设已经知道第 \(k\) 大的边权为 \(w\)，则我们可以把边权大于等于 \(w\) 的边的边权 \(x\) 全部变成 \(x-w\)，小于 \(w\) 的边权全部变成 \(0\)，再跑最短路。答案就是 \(d_n + k \times w\)。其中 \(d_n\) 表示 \(1 \to n\) 的在新图上的最短路长度。

但是现在我们不知道真正的第 \(k\) 大的边权是多少，我们考虑稀里糊涂的枚举每一条边，把它当作第 \(k\) 大的边权再来跑，得到的结果对答案的影响。

为了方便证明，我们先符号化一下。

按题目中的符号 \(1 \to n\) 的一条路径上有 \(l\) 条边，依次记为 \(c_1,c_2,\cdots,c_l\)，不妨令 \(c_1 \ge c_2 \ge \cdots \ge c_l\)。

真实的答案 \(A= \sum \limits_{i=1} ^k c_i = \sum \limits _{i=1 } ^l \max (c_i -c_k ,0) + k \times c_k\)，我们钦定第 \(t\) 条边为第 \(k\) 大的边后得到的答案 \(A_t = \sum \limits _{i=1 } ^l \max (c_i -c_t ,0) + k \times c_t\)。

1. \(c_t = c_k\)，显然 \(A=A_t\)。
2. \(c_t < c_k \Rightarrow t>k\)，即我们钦定的这条边更小。

\[\begin{align*} A - A_t &= \sum _{i=1} ^ l \big [ \max(c_i-c_k,0) -\max(c_i- c_t,0) \big ] + k \times ( c_k-c_t)\\ &= \sum _{i=1} ^k [(c_i - c_k) - (c_i - c_t)] + \sum _{i=k+1} ^t [0 - (c_i - c_t)] + \sum _{i=t+1} ^l [0-0] + k \times ( c_k-c_t)\\ &=k \times ( c_t-c_k) + \sum _{i=k+1} ^t (c_t-c_i) + k \times ( c_k-c_t) \\ &= \sum _{i=k+1} ^t (c_t-c_i) \end{align*} \]

由 \(i \le t \Rightarrow c_i \ge c_t\)，故 \(A \le A_t\)。

3. \(c_t > c_k \Rightarrow t < k\)，即我们钦定的边更大。

\[\begin{align*} A - A_t &= \sum _{i=1} ^ l \big [ \max(c_i-c_k,0) -\max(c_i- c_t,0) \big ] + k \times ( c_k-c_t)\\ &=\sum _{i=1 } ^t [(c_i - c_k) - (c_i - c_t)] + \sum _{t+1} ^ k [(c_i - c_k) - 0] + \sum _{i=k+1} ^ l [0-0] + k \times ( c_k-c_t)\\ &= t \times (c_t- c_k ) + \sum _{t+1} ^ k (c_i - c_k) + k \times ( c_k-c_t) \\ &= \sum _{i=t+1} ^ k (c_i - c_k +c_k-c_t) \\ &= \sum _{i=t+1} ^ k (c_i -c_t) \end{align*} \]

由 \(i > t \Rightarrow c_i \le c_t\)，故 \(A \le A_t\)。

综上所述，\(\forall 1 \le t \le l,A \le A_t\)，且 \(\exist 1 \le t \le l,A=A_t\)。该结论对于每一条路径都成立，而我们又是在求最短路，所以答案一定能取到。证毕！

用 dijkstra 实现最短路，复杂度为 \(\Theta(m^2 \log n)\)。

最后放一下代码。

#include <bits/stdc++.h>
using namespace std;
const int N=3e3+10;
using ll=long long;
namespace Graph{
    struct _edge{
        int v,nxt,w;
    }es[N*2];
    int head[N],gcnt;
    using pii=pair<ll,int>;
    ll dis[N];
    bool vis[N];
    priority_queue<pii,vector<pii>,greater<pii> >pq;
    void add_edge(int u,int v,int w){
        es[++gcnt]={v,head[u],w};head[u]=gcnt;
    }
    void clear(){
        memset(head,0,sizeof head);
        gcnt=0;
    }
    void dijkstra(int s){
        memset(dis,0x3f,sizeof dis);
        memset(vis,0,sizeof vis);
        dis[s]=0;
        pq.emplace(0,s);
        while(!pq.empty()){
            int u=pq.top().second;pq.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(int i=head[u];i;i=es[i].nxt){
                int v=es[i].v;
                if(dis[v]>dis[u]+es[i].w){
                    dis[v]=dis[u]+es[i].w;
                    pq.emplace(dis[v],v);
                }
            }
        }
    }
}
struct edge{
    int u,v,w;
}Es[N];
int n,m,K;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>K;
    for(int i=1;i<=m;i++) cin>>Es[i].u>>Es[i].v>>Es[i].w;
    ll ans=0x3ff3f3f3f3f3f3f;
    for(int i=0;i<=m;i++){
        Graph::clear();
        for(int j=1;j<=m;j++){
            if(Es[j].w<Es[i].w){
                Graph::add_edge(Es[j].u,Es[j].v,0);
                Graph::add_edge(Es[j].v,Es[j].u,0);
            }else{
                Graph::add_edge(Es[j].u,Es[j].v,Es[j].w-Es[i].w);
                Graph::add_edge(Es[j].v,Es[j].u,Es[j].w-Es[i].w);
            }
        }
        Graph::dijkstra(1);
        ans=min(ans,Graph::dis[n]+1ll*K*Es[i].w);
    }
    printf("%lld\n",ans);
    return 0;
}