专栏文章

题解：P13271 [NOI2025] 机器人

tthy21171
P13271题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miouu5yn
此快照首次捕获于
2025/12/03 01:31
3 个月前
此快照最后确认于
2025/12/03 01:31
3 个月前
查看原文
考虑如何建图。
首先，我们可以关注到了一个良好的条件：∑i=1ndi=m\sum\limits_{i=1}^nd_i=m。（废话）
于是考虑拆点，设 Pi,jP_{i,j} 表示机器人到达点 ii，且 p=jp=j 时的状态。
显然，对于一个点 Pi,jP_{i,j}，最多向其他点连 33 条边。（设 v=yi,j,w=zi,jv=y_{i,j},w=z_{i,j}）
1.当 j>1j>1 时，Pi,j→Pi,j−1P_{i,j}\to P_{i,j-1}，边权为 wjw_j。
2.当 j<dij<d_i 时，Pi,j→Pi,j+1P_{i,j}\to P_{i,j+1}，边权为 vjv_j。
3.Pi,j→Pv,jP_{i,j}\to P_{v,j}，边权为 zi,jz_{i,j}。这里有一个细节，当 j>dvj>d_v 时，我们是没有 Pv,jP_{v,j} 这个点的（jj 太大了，而点 vv 只有 dvd_v 条边）。
所以当 j>dvj>d_{v} 时，我们要将点 Pi,jP_{i,j} 连向 Pv,dvP_{v,d_v}，边权为 w+∑i=dv+1jwiw+\sum\limits_{i=d_v+1}^jw_i。
所以，这样建图边的数量就是 O(m)O(m) 级别的。
最后跑一遍 dijkstra\text{dijkstra} 时间复杂度 O(mlog⁡m)O(m\log m)。
CPP
#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;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...