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

SunburstFan · 2025-05-10 15:03:28 · 题解

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

题目大意

你被困在一个有 n 个房间和 m 条双向隧道构成的地牢中。隧道地板上覆盖着温度为 c 的熔岩，只有当你的耐热靴子冷却等级恰好等于 c 时，才能安全经过。你从房间 1 出发，初始冷却等级为 0，在房间内可以花费硬币调整冷却等级（每增加或减少 1 需 1 枚金币），目标是以最小金币花费到达房间 n。

解题思路

方案核心在于将问题转化为求一条路径上温度调整的最小成本。对于一条选定的路径，如果依次经过温度 c_1, c_2, …, c_k 的隧道，总花费为 |c_1 − 0| + |c_2 − c_1| + … + |c_k − c_{k-1}|。

考虑每个房间内相邻隧道的温度调整问题：

• 对于同一个房间，把所有出入该房间的隧道按温度排序，任意相邻两隧道间调整的花费即为它们温度之差。
• 从房间 1 出发，初始冷却等级为 0，因此进入该房间的每条隧道的起始花费为隧道温度。
• 对于房间 n，只需保证通过某条隧道到达即可。

因此，我们构造一个以隧道为“节点”的图，

• 对于每个房间，将该房间中排序后的隧道节点两两建立边，权值为温度差（双向边）。
• 接着，对于所有出自房间 1 的隧道，初始代价为它们各自的温度；对于所有经过房间 n 的隧道，记录到达终点的代价。

最后，利用 Dijkstra 在该图上求最短路径，答案即为最低总调整花费。

该方法在构造边时对每个房间按隧道温度排序，所以整体时间复杂度为 O(m\times \log m)。

#include<bits/stdc++.h>
using  namespace std;

#define ll long long
const ll INF=1e18;

struct edge{
    int u,v,c,id;
};

namespace sunburstfan{
    vector<edge> e;
    vector<vector<int> >raw_e;
    vector<vector<pair<int,ll> > > G;

    bool cmp(int a,int b){
        return e[a-1].c<e[b-1].c;
    }

    ll Dij(int n){
        vector<ll> dis(e.size()+1,INF);
        priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;

        for(auto u:raw_e[1]){
            dis[u]=e[u-1].c;
            pq.push({dis[u],u});
        }

        while(!pq.empty()){
            auto p=pq.top(); pq.pop();

            ll u=p.second,c=p.first;
            if(c>dis[u]) continue;

            for(auto v:G[u]){
                if(dis[v.first]>dis[u]+v.second){
                    dis[v.first]=dis[u]+v.second;
                    pq.push({dis[v.first],v.first});
                }
            }

        }

        ll ans=INF;
        for(auto u:raw_e[n]){
            if(dis[u]!=INF){
                ans=min(ans,dis[u]);
            }
        }

        return ans;
    }

}
using namespace sunburstfan;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>n>>m;

    if(n==1){
        cout<<0<<"\n";
        return 0;
    }

    raw_e.resize(n+1),G.resize(m+1);
    for(int i=1;i<=m;i++){
        int u,v,c;
        cin>>u>>v>>c;

        e.push_back({u,v,c,i});
        raw_e[u].push_back(i);
        raw_e[v].push_back(i);
    }   

    for(int i=1;i<=n;i++){
        sort(raw_e[i].begin(),raw_e[i].end(),cmp);

        for(int j=1;j<raw_e[i].size();j++){
            int u=raw_e[i][j-1],v=raw_e[i][j];
            ll c=abs(e[v-1].c-e[u-1].c);

            G[u].push_back({v,c});
            G[v].push_back({u,c});
        }
    }

    cout<<Dij(n)<<"\n";

    return 0;
}