题解：P13271 [NOI2025] 机器人

· · 题解

更新

这是一篇已通过的题解。

思路

首先看到的是 n 个点 m 条边，可以想到跑最短路。然后发现还有一个参数 p，限制只能走每个点的第 p 条边。
所以每个点有两个状态：第 i 个点，参数 p。多个状态的最短路问题用分层图解决。

转移共分为两种：

  1. 同一个点内转移，即 i 不变，p 变。
  2. 不同点间转移，即 i 变，p 不变。

这样太麻烦了，不如每次转移 i,p 一起变。具体而言，先变 i，再变 p。
变 i 的时候 p 没变，所以只有一条路可以走，变完之后的 i' 是确定的，花费也是确定的。
变后的 p' 要能继续转移，所以 p' 不能大于 d_{i'}。在 1\sim d_{i'} 内枚举 p' 即可。
变 p 产生的花费是 v_i 或 w_i 内某一段的和，可以用前缀和来求。

有个例外，我们也可以只变 i，不变 p，并且之后不再用这个状态转移了，那么就不用关心 p' 是否大于 d_{i'}。我们可以把这种例外全部看作 p'=0 的特殊情况。

每次转移的花费为非负整数，可以使用 dijkstra 求最短路。
最后对每个点，统计 p 取 0\sim d_i 花费的最小值即可。

时间复杂度为 O((n+m)\log (n+m))。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,pii> plii;
const int MAXN=3e5+3;
const ll Inf=1e18;

int n,m,k,d[MAXN];
vector<pii>edg[MAXN];
vector<ll>dis[MAXN];
vector<bool>vis[MAXN];
priority_queue<plii>q;

ll sumv[MAXN],sumw[MAXN];
ll gs(int x,int y){
    if(x<y)return sumv[y-1]-sumv[x-1];
    else return sumw[x]-sumw[y];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int c; cin>>c>>n>>m>>k;
    for(int i=1;i<k;i++){
        cin>>sumv[i];
        sumv[i]+=sumv[i-1];
    }
    for(int i=2;i<=k;i++){
        cin>>sumw[i];
        sumw[i]+=sumw[i-1];
    }
    for(int i=1;i<=n;i++){
        cin>>d[i];
        vis[i].assign(d[i]+1,0);
        dis[i].assign(d[i]+1,Inf);
        edg[i].assign(d[i]+1,{0,0});
        for(int j=1;j<=d[i];j++){
            int y,z; cin>>y>>z;
            edg[i][j]={y,z};
        }
    }
    for(int i=1;i<=d[1];i++){
        dis[1][i]=gs(1,i);
        q.push({-dis[1][i],{1,i}});
    }
    while(!q.empty()){
        pii pos=q.top().second; q.pop();
        int fr=pos.first,p=pos.second;
        if(vis[fr][p])continue;
        vis[fr][p]=1;
        int to=edg[fr][p].first;
        ll cost0=dis[fr][p]+edg[fr][p].second;
        dis[to][0]=min(dis[to][0],cost0);
        for(int i=1;i<=d[to];i++){
            ll cost=cost0+gs(p,i);
            if(cost<dis[to][i]){
                dis[to][i]=cost;
                q.push({-cost,{to,i}});
            }
        }
    }
    for(int i=1;i<=n;i++){
        sort(dis[i].begin(),dis[i].end());
        cout<<(dis[i][0]==Inf?-1:dis[i][0])<<' ';
    }
    return 0;
}