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

ELECTRODE_kaf · 2025-03-12 18:00:01 · 题解

总花费是答案路径上所有相邻边的权值之差，所以由此可以推出部分分的做法：把原图中所有边当做点建一个新图，连接共点边作为新边，权值为原图中边权之差。建一个超级源点和一个超级汇点，跑最短路即可。

优化比较明确：在一个点上改变自身权值多次，只要始末态不变，花费就不变，所以只需要给原图中的点的连边按照边权排序，给排位相邻的边建新边即可，其它的边可以通过这些边中转，结果不变。

记得把初始值开大一点哦～

const ll N=2e5+10;
ll n,m;
vector<pll> g[N],gg[N];

void input() {
//  freopen("P11860_2.in.txt","r",stdin);
    cin>>n>>m;

    rep(i,1,m) {
        ll u,v,w;
        cin>>u>>v>>w;
        g[u].pb({w,i});
        g[v].pb({w,i});
    }
}

void instruct() {
    rep(i,2,n-1) {
        sort(g[i].begin(),g[i].end());

        rep(j,1,g[i].size()-1) {
            ll u=g[i][j].se,v=g[i][j-1].se,w=abs(g[i][j].fi-g[i][j-1].fi);
            gg[u].pb({v,w});
            gg[v].pb({u,w});
        }
    }

    for(pll i:g[1]) {
        ll u=0,v=i.se,w=i.fi;
        gg[u].pb({v,w});
        gg[v].pb({u,w});
    }

    for(pll i:g[n]) {
        ll u=m+1,v=i.se,w=0;
        gg[u].pb({v,w});
        gg[v].pb({u,w});
    }

//  rep(i,0,m+1){
//      cout<<"i="<<i<<":";
//      
//      for(pll j:gg[i]) cout<<j.fi<<' ';
//      
//      endl;
//  }
//  
//  pause;
}

const ll inf=922337203685477580;
ll ans[N];
bool vis[N];
pqueue(pll,greater) pq;

void dij(){
    rep(i,1,m+1) ans[i]=inf;

    pq.push({0,0});

    while(pq.empty()==0){
        pll cur;
        xtop(cur,pq);

        if(vis[cur.se]) ctn;
        else vis[cur.se]=1;

        for(pll i:gg[cur.se]) {
//          update(ans[i.fi],cur.fi+i.se,min);

            if(cur.fi+i.se<ans[i.fi]){
                ans[i.fi]=cur.fi+i.se;
                pq.push({ans[i.fi],i.fi});
            }
        }
    }

//  cout<<"ans[]:";
//  
//  rep(i,0,m+1) cout<<ans[i]<<' ';
//  
//  endl;
//  pause;
}

void output(){
    cout<<ans[m+1];
}

int main() {
    input();
    instruct();
    dij();
    output();
}