[NOI2025] 机器人

_H17_ · 2025-07-14 19:51:41 · 题解

致歉

:::info[致歉]{open} 之前的代码由于我对分层图连边经验匮乏，并且疏忽，导致边数爆炸，已经更正，如果有错误欢迎指出。详见这里。 :::

题目分析

看了眼题，好像会做？没数据能不能直接切有点悬啊，不过错了的话会更新题解，如果没更新大概是对的。

首先发现是求最短路，还要分层图。

显然肯定是按照 p 分层做最短路，但是有一个问题点数变成了 n\times k，显然无法通过。

注意到如果 p>d_i 那没法连出去，考虑只对 1\sim d_i 建图，这样就可以规避这个问题，点数是 n+m（每个点肯定有点，而且还有 d_i 个层，分层的点一共 m，不分的按照 n，应该卡不满，卡满了也没事）。

每次可以自己花代价更改 p 来松弛，也可以去其它点的方式松弛。代价可以前缀和处理。

因为权值非负，剩下 Dijkstra 即可。

时间复杂度 O(n+k+m\log\min(n+m,n\times k))（前面是输入）。

需要注意同一个点不同层连边只需要连接相邻的层，不然边数是 O(m^2) 的，大家做分层图最短路记得多考虑一下连边的正确性。

代码实现

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long 
using namespace std;
using namespace __gnu_pbds;
constexpr int N=3e5+1;
int id,n,m,k,v[N],w[N],oud[N],ans[N];
gp_hash_table<int,int>dis[N],vis[N];
vector<pair<int,int> >e[N];
void add(int u,int v,int w){
    e[u].push_back({v,w});
    return;
}
int up(int x,int y){
    return v[y-1]-v[x-1];
}
int down(int x,int y){
    return w[x]-w[y];
}
void dijkstra(){
    std::priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >q;
    q.push({dis[1][1]=0,{1,1}});
    ans[1]=0,vis[1][1]=1;
    while(!q.empty()){
        auto[d,H17]=q.top();
        auto[u,p]=H17;
        q.pop();
        if(dis[u][p]!=d)
            continue;
        if(p!=1&&oud[u]){
            int val=(p>oud[u]?oud[u]:p-1);
            if(!vis[u][val]||d+down(p,val)<dis[u][val]){
                q.push({dis[u][val]=d+down(p,val),{u,val}});
                vis[u][val]=1;
            }
        }
        if(p<min(k,oud[u])){
            if(!vis[u][p+1]||d+up(p,p+1)<dis[u][p+1]){
                q.push({dis[u][p+1]=d+up(p,p+1),{u,p+1}});
                vis[u][p+1]=1;
            }
        }
        if(oud[u]<p)
            continue;
        auto[v,w]=e[u][p-1];
        if(!vis[v][p]||d+w<dis[v][p]){
            q.push({dis[v][p]=d+w,{v,p}});
            ans[v]=min(ans[v],dis[v][p]);
            vis[v][p]=1;
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>id>>n>>m>>k;
    for(int i=1;i<k;i++){
        cin>>v[i];
        v[i]+=v[i-1];
    }
    for(int i=2;i<=k;i++){
        cin>>w[i];
        w[i]+=w[i-1];
    }
    for(int u=1,v,w;u<=n;u++){
        cin>>oud[u];
        for(int i=1;i<=oud[u];i++){
            cin>>v>>w;
            add(u,v,w);
        }
    }
    memset(ans,0x3f,sizeof(ans));
    dijkstra();
    for(int i=1;i<=n;i++)
        cout<<(ans[i]!=0x3f3f3f3f3f3f3f3fll?ans[i]:-1)<<' ';
    return 0;
}