自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 21:39:59，当前版本为作者最后更新于2022-12-15 08:06:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有点无趣的题目。

这题是 P1606 的加强版。大部分思路与那题一致。

对于每个点，将它向它能直接或通过荷叶间接到达的点连一条有向边。如果连向水的话边权为 1，连向铂金的话边权为 2。

跑最短路，顺便维护一下方案数，铂金最大值和铂金方案数。总体思路和 P1606 几乎没有差别。（所以我昨天为什么闲的没事在那里敲 A*）

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pid(x, y) ((x - 1) * n + (y - 1))
int m, n, p;
struct Edge {
	int to, next, w;
} e[200005];
int head[905], len;
void Insert(int u, int v, int w) {
	e[++len].to = v;
	e[len].next = head[u];
	e[len].w = w;
	head[u] = len;
}
int mp[905];
int sx, sy, tx, ty;
int d[905], pt[905];
ll f[905], g[905];
bool vis[905], mkd[905];
struct ND {
	int num, dis;
	bool operator<(const ND &o) const {
		return dis > o.dis;
	}
};
void dfs(int x, int y, int rx, int ry) {
	vis[pid(x, y)] = true;
	int dx[] = {2, 2, -2, -2, 1, 1, -1, -1};
	int dy[] = {1, -1, 1, -1, 2, -2, 2, -2};
	for (int i = 0; i < 8; i++) {
		if (x + dx[i] < 1 || x + dx[i] > m || y + dy[i] < 1 || y + dy[i] > n) continue;
		if (mp[pid(x + dx[i], y + dy[i])] == 0) {
			if (!mkd[pid(x + dx[i], y + dy[i])]) Insert(pid(rx, ry), pid(x + dx[i], y + dy[i]), 1);
			mkd[pid(x + dx[i], y + dy[i])] = true;
		}
		else if (mp[pid(x + dx[i], y + dy[i])] == 4) {
			if (!mkd[pid(x + dx[i], y + dy[i])]) Insert(pid(rx, ry), pid(x + dx[i], y + dy[i]), 0);
			mkd[pid(x + dx[i], y + dy[i])] = true;
		}
		else if (mp[pid(x + dx[i], y + dy[i])] == 5) {
			if (!mkd[pid(x + dx[i], y + dy[i])]) Insert(pid(rx, ry), pid(x + dx[i], y + dy[i]), 2);
			mkd[pid(x + dx[i], y + dy[i])] = true;
		}
		else if (mp[pid(x + dx[i], y + dy[i])] == 1) {
			if (!vis[pid(x + dx[i], y + dy[i])]) dfs(x + dx[i], y + dy[i], rx, ry);
		}
	}
}
void Dijkstra() {
	priority_queue<ND> q;
	q.push({pid(sx, sy), 0});
	memset(d, 0x3f, sizeof(d));
	d[pid(sx, sy)] = 0;
	f[pid(sx, sy)] = 1;
	g[pid(sx, sy)] = 1;
	while (!q.empty()) {
		int u = q.top().num; q.pop();
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].to;
			if (d[v] == d[u] + e[i].w) {
				f[v] += f[u];
				if (pt[v] == pt[u] + (e[i].w == 2)) {
					g[v] += g[u];
				}
				else if (pt[v] < pt[u] + (e[i].w == 2)) {
					pt[v] = pt[u] + (e[i].w == 2);
					g[v] = g[u];
				}
			}
			else if (d[v] > d[u] + e[i].w) {
				d[v] = d[u] + e[i].w;
				f[v] = f[u];
				g[v] = g[u];
				pt[v] = pt[u] + (e[i].w == 2);
				q.push({v, d[v]});
			}
		}
	}
}
int main() {
	scanf("%d%d%d", &p, &m, &n);
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &mp[pid(i, j)]);
			if (mp[pid(i, j)] == 3) {
				sx = i; sy = j;
				mp[pid(i, j)] = 0;
			}
			else if (mp[pid(i, j)] == 4) {
				tx = i; ty = j;
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			memset(vis, 0, sizeof(vis));
			memset(mkd, 0, sizeof(mkd));
			if (mp[pid(i, j)] == 0 || mp[pid(i, j)] == 5) dfs(i, j, i, j);
		}
	}
	Dijkstra();
	if (d[pid(tx, ty)] > p) {
		puts("-1");
		return 0;
	}
	printf("%d %lld\n", d[pid(tx, ty)], f[pid(tx, ty)]);
	if (!pt[pid(tx, ty)]) {
		puts("-1");
		return 0;
	}
	printf("%d %lld\n", pt[pid(tx, ty)], g[pid(tx, ty)]);
	return 0;
}