题解：P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava

· · 题解

题解

这道题其实是这个题改了点。

但作为负责任的题解，我还是要讲讲这种题怎么做。

首先发现走的花费只与边权的相对关系有关，那么我们考虑一个很典的结论：

把边看成点。

具体来说，我们设正边为 i，反边为 i+m。

然后可以直接把从一个点出发的边两两连接，那么边权显然就是两条边权的差的绝对值。

但是我们发现，通过上面这么处理之后，我们只连了从某个点出去的边之间的关系，也就是说，我们没有把正反边联系起来。

在这道题中，由于花费只是差值（在我给的原题更麻烦），所以我们把每一条边的正反边之间连一条权值为 0 的边即可。

然后，我们再把 0 号点（即虚拟的出发点）连上从 1 号点出发的边。把从 n 号点出发的边连上 m+m+1 号点（即虚拟的结束点）。

然后我们发现，光建图的复杂度就是 O(\sum_{i=1}^n d_i^2)（d_i 是出度）了。显然如果图是菊花就爆了，那么我们考虑把一个点的出边按边权排序，然后只加相邻的双边，权值为 w_i-w_{i-1}。

考虑为什么这么做是对的。显然，我在经过某个点时，一定是从一条出边走到另一条出边。那么，我经过的权值就是两条边权值的差。而在我们刚刚提到的建图方法中，如果我要从权值为 w_i 走到 w_j，那么花费即为：

(w_{i+1}-w_i)+(w_{i+2}-w_{i+1})+...+(w_{j-1}-w_{j-2}) +(w_{j}-w_{j-1})

发现中间全部被约掉了，就剩：

w_j-w_i

满足题意。 而且易证得这种方式可以表示出任意的走法。

那么有人就问了：我们建了环为什么他不会走回头路呢？

因为我们等会跑的是最短路，显然走回头路不优，也就不会走到。

AC_Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<long long, long long>
#define xx first
#define yy second
const int N = 4e5 + 10;//注意两边空间
int n, m, dis[N];
vector<PII> G[N], H[N];
bool sure[N];
priority_queue<PII, vector<PII>, greater<PII>> q; 
void dij(){
    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0;
    q.push({0, 0});
    while(!q.empty()){
        auto u = q.top();
        q.pop();
        if(sure[u.yy])continue;
        sure[u.yy] = 1;
        for(auto v : H[u.yy]){
            if(dis[v.xx] > dis[u.yy] + v.yy){
                dis[v.xx] = dis[u.yy] + v.yy;
                q.push({dis[v.xx], v.xx});
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({w, i});
        G[v].push_back({w, i + m});
        H[i].push_back({i + m, 0});
        H[i + m].push_back({i, 0});//正反边
    }
    for(int i = 1; i <= n; i ++){
        sort(G[i].begin(), G[i].end());//边权排序
        for(int j = 0; j < G[i].size() - 1; j ++){
            H[G[i][j].yy].push_back({G[i][j + 1].yy, G[i][j + 1].xx - G[i][j].xx});
            H[G[i][j + 1].yy].push_back({G[i][j].yy, G[i][j + 1].xx - G[i][j].xx});
        }//加相邻的边
    }
    for(auto i : G[1])H[0].push_back({i.yy, i.xx});
    for(auto i : G[n])H[i.yy].push_back({m + m + 1, 0});//起点终点
    dij();
    cout << dis[m + m + 1];
    return 0;
}

完结撒花。