题解 P2644 白金莲花池

251Sec · 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;
}