题解：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。

\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。

\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)。

最后放一下代码。

:::success[code]{open}

#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;
}

:::