题解：P13271 [NOI2025] 机器人

thy21171 · 2025-07-17 21:48:13 · 题解

考虑如何建图。

首先，我们可以关注到了一个良好的条件：\sum\limits_{i=1}^nd_i=m。（废话）

于是考虑拆点，设 P_{i,j} 表示机器人到达点 i，且 p=j 时的状态。

显然，对于一个点 P_{i,j}，最多向其他点连 3 条边。（设 v=y_{i,j},w=z_{i,j}）

1.当 j>1 时，P_{i,j}\to P_{i,j-1}，边权为 w_j。

2.当 j<d_i 时，P_{i,j}\to P_{i,j+1}，边权为 v_j。

3.P_{i,j}\to P_{v,j}，边权为 z_{i,j}。这里有一个细节，当 j>d_v 时，我们是没有 P_{v,j} 这个点的（j 太大了，而点 v 只有 d_v 条边）。

所以当 j>d_{v} 时，我们要将点 P_{i,j} 连向 P_{v,d_v}，边权为 w+\sum\limits_{i=d_v+1}^jw_i。

所以，这样建图边的数量就是 O(m) 级别的。

最后跑一遍 \text{dijkstra} 时间复杂度 O(m\log m)。

#include <bits/stdc++.h>
typedef long long ll;
const int N = 3e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m, k, s, vis[N], to[N];
ll V[N], W[N];
std::vector<std::pair<int, ll>> Q[N];
ll ans[N], dis[N];

struct Node { 
    ll dis; int u, p; 
    bool operator< (Node a) const { return dis > a.dis; }
};

std::priority_queue<Node> que;

int main()
{
    std::memset(ans, 0x3f, sizeof(ans));
    std::memset(dis, 0x3f, sizeof(dis));

    scanf("%*d%d%d%d", &n, &m, &k); ans[1] = dis[1] = 0;
    for (int i = 1; i < k; ++i) scanf("%lld", V + i), V[i] += V[i - 1];
    for (int i = 2; i <= k; ++i) scanf("%lld", W + i), W[i] += W[i - 1];

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s); 
        for (int j = 1, v, w; j <= s; ++j)
            scanf("%d%d", &v, &w), Q[i].emplace_back(v, w);
        to[i + 1] = to[i] + s;
    }

    if (Q[1].empty()) { // 特判 d[1] = 0 的情况，但貌似数据没有卡这个？
        printf("0");
        for (int i = 2; i <= n; ++i)
            printf(" -1");
        return 0;
    }

    que.push({0, 1, 1});

    while (!que.empty()) {
        auto [d, u, p] = que.top(); que.pop();
        if (vis[to[u] + p]) continue; vis[to[u] + p] = 1;

        auto [v, w] = Q[u][p - 1]; int q = Q[v].size();
        ans[v] = std::min(ans[v], dis[to[u] + p] + w);

        if (q >= p) {
            if (dis[to[u] + p] + w < dis[to[v] + p]) {
                dis[to[v] + p] = dis[to[u] + p] + w;
                if (!vis[to[v] + p]) que.push({dis[to[v] + p], v, p});
            }
        } else if (q) {
            w += W[p] - W[q]; 
            if (dis[to[u] + p] + w < dis[to[v] + q]) {
                dis[to[v] + q] = dis[to[u] + p] + w;
                if (!vis[to[v] + q]) que.push({dis[to[v] + q], v, q});
            }
        }

        if (p < Q[u].size()) {
            w = V[p] - V[p - 1]; q = p + 1;
            if (dis[to[u] + p] + w < dis[to[u] + q]) {
                dis[to[u] + q] = dis[to[u] + p] + w;
                if (!vis[to[u] + q]) que.push({dis[to[u] + q], u, q});
            }
        }

        if (p > 1) {
            w = W[p] - W[p - 1]; q = p - 1;
            if (dis[to[u] + p] + w < dis[to[u] + q]) {
                dis[to[u] + q] = dis[to[u] + p] + w;
                if (!vis[to[u] + q]) que.push({dis[to[u] + q], u, q});
            }
        }
    }

    for (int i = 1; i <= n; ++i)
        printf("%lld ", ans[i] == INF ? -1 : ans[i]);

    return 0;
}