UVa 12202 Haunted Graveyard

2026-02-01 11:57:48 栏目：帮助文档 6 阅读

题目描述

万圣节之夜，胆小的约翰需要穿越一个 $W \times H$ 的墓地网格。入口在 $(0, 0)$ ，出口在 $(W - 1, H - 1)$ 。每个单元格可能是：

草地：可以正常通过，耗时 $1$ 秒移动到相邻单元格（上下左右）
墓碑：无法通过
鬼洞：进入后会被传送到另一个位置 $X_2, Y_2)$ ，并产生时间差 $T$ （ $T$ 可为负、零或正）

如果 $T < 0$ ，意味着时间倒流（提前到达目的地）。约翰希望能够尽快到达出口，但如果存在无限回到过去的可能性（即存在时间可以无限减少的路径），程序必须报告这种情况。

输入格式

多组测试用例。每组：

第一行： $W$ 和 $H$ （ $1 \leq W, H \leq 30$ ）
第二行：墓碑数 $G$ （ $G \geq 0$ ）
接下来 $G$ 行：每个墓碑的坐标 $(X, Y)$
下一行：鬼洞数 $E$ （ $E \geq 0$ ）
接下来 $E$ 行： $X_1 Y_1 X_2 Y_2 T$ ，表示从 $X_1,Y_1)$ 到 $X_2,Y_2)$ 的鬼洞，时间差为 $T$

保证：

没有两个鬼洞起点相同
鬼洞目的地没有墓碑
起点 $(0, 0)$ 和终点 $(W - 1, H - 1)$ 没有墓碑或鬼洞

输入以 0 0 结束。

输出格式

对于每组测试用例：

如果存在无限回到过去的可能，输出 Never
否则，如果无法到达终点，输出 Impossible
否则，输出最短时间（秒）

题目分析

问题本质

这是一个带负权边的单源最短路径问题：

节点：每个网格单元格，共 $W \times H$ 个，编号为 $i d = y \times W + x$
边：
1. 普通移动 ：从当前单元格到相邻四个方向（如果可走），权值 $1$
2. 鬼洞：从起点到目的地，权值 $T$ （ $T$ 可能为负）
特殊约束 ：
- 墓碑单元格不可进入（不添加入边）
- 终点 $(W - 1, H - 1)$ 不再向外移动
- 有鬼洞的单元格只使用鬼洞边，不添加普通移动边

关键挑战：负权环

如果图中存在从起点可达的负权环，那么约翰可以在这个环上无限循环，时间无限减少，对应题目中“无限回到过去”的情况。根据题目要求，一旦检测到这种情况，无论终点是否可达，都应输出 Never 。

算法选择

对于带负权边的图，常用的算法是 $Bellman-Ford$ 算法 ，它可以：

求出单源最短路径（在无负权环的情况下）
检测是否存在从源点可达的负权环

由于 $W \times H \leq 900$ ，边数最多约为 $4 \times 900 + E \leq 3600 + 900 = 4500$ ， $Bellman-Ford$ 的复杂度 $O (V E)$ 在可接受范围内。

解题思路

步骤一：建模与建图

标记特殊单元格 ：
- 用数组 gravestone[x][y] 标记墓碑
- 用数组 hole[x][y][0..2] 存储鬼洞信息（目标 $x$ 、目标 $y$ 、时间差 $T$ ）
建图规则 ：
- 遍历每个单元格 $(x, y)$
- 如果是墓碑或终点：跳过（不添加出边）
- 如果有鬼洞：添加一条从 $(x, y)$ 到鬼洞目的地的边，权值为 $T$
- 否则（草地）：向四个方向添加普通移动边，权值为 $1$ （确保目标单元格在网格内且不是墓碑）

步骤二： $Bellman-Ford$ 算法

初始化 ：
- dist[0] = 0 （起点）
- 其他节点 dist[i] = INF
松弛操作 ：
- 执行 $V - 1$ 次（ $V = W \times H$ ）松弛
- 每次遍历所有边，如果 dist[from] + cost < dist[to] ，则更新
- 如果某次松弛没有更新，可以提前结束
检测负环 ：
- 再进行一次松弛遍历
- 如果还能更新某个节点的距离，说明存在负环
- 重要：只关心从起点可达的负环，因此检查时需确保 dist[from] < INF

步骤三：输出决策

如果检测到从起点可达的负环 → Never
否则，如果 dist[终点] == INF → Impossible
否则 → dist[终点]

注意事项

鬼洞自环 ：鬼洞的起点和终点可以相同（ $X_1=X_2, Y_1=Y_2$ ），如果 $T < 0$ ，就是一个自环负权边，构成负环
终点处理 ：终点 $(W - 1, H - 1)$ 不添加任何出边，因为到达终点后立即离开
可达性检查 ：负环必须从起点可达才报告 Never ，否则不影响结果
墓碑阻挡 ：墓碑单元格不被视为图中的节点（没有入边）

复杂度分析

时间复杂度： $O (V E) \approx O ((W \times H) \times (4 W H + E))$ ，最大约 $10^6$ ，可以接受
空间复杂度： $O (W H + E)$ ，主要用于存储图和距离数组

代码实现

// Haunted Graveyard
// UVa ID: 12202
// Verdict: Accepted
// Submission Date: 2026-01-10
// UVa Run Time: 0.030s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include 
using namespace std;

struct Edge {
    int from, to, cost;
};

const int INF = 1e9;
const int MAX_N = 905; // 最大节点数：30*30=900

int W, H, G, E;
int gravestone[32][32]; // 标记墓碑
int hole[32][32][3];    // hole[x][y][0/1/2] -> 目标x, 目标y, 时间差
int dist[MAX_N];
vector<Edge> edges;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> W >> H, W || H) {
        memset(gravestone, 0, sizeof gravestone);
        memset(hole, -1, sizeof hole); // -1 表示没有鬼洞
        edges.clear();

        // 读入墓碑
        cin >> G;
        for (int i = 0; i < G; ++i) {
            int x, y;
            cin >> x >> y;
            gravestone[x][y] = 1;
        }

        // 读入鬼洞
        cin >> E;
        for (int i = 0; i < E; ++i) {
            int x1, y1, x2, y2, t;
            cin >> x1 >> y1 >> x2 >> y2 >> t;
            hole[x1][y1][0] = x2;
            hole[x1][y1][1] = y2;
            hole[x1][y1][2] = t;
        }

        // 建图
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int x = 0; x < W; ++x) {
            for (int y = 0; y < H; ++y) {
                int u = y * W + x;
                // 如果是终点或墓碑，不添加普通移动边
                if (x == W - 1 && y == H - 1) continue;
                if (gravestone[x][y]) continue;

                // 如果该格有鬼洞，只添加鬼洞边
                if (hole[x][y][0] != -1) {
                    int x2 = hole[x][y][0], y2 = hole[x][y][1], t = hole[x][y][2];
                    int v = y2 * W + x2;
                    edges.push_back({u, v, t});
                } else {
                    // 否则添加普通移动边
                    for (int d = 0; d < 4; ++d) {
                        int nx = x + dirs[d][0], ny = y + dirs[d][1];
                        if (nx >= 0 && nx < W && ny >= 0 && ny < H && !gravestone[nx][ny]) {
                            int v = ny * W + nx;
                            edges.push_back({u, v, 1});
                        }
                    }
                }
            }
        }

        // Bellman-Ford
        int V = W * H;
        fill(dist, dist + V, INF);
        dist[0] = 0;

        // 执行 V-1 次松弛
        for (int i = 0; i < V - 1; ++i) {
            bool updated = false;
            for (const Edge& e : edges) {
                if (dist[e.from] < INF && dist[e.to] > dist[e.from] + e.cost) {
                    dist[e.to] = dist[e.from] + e.cost;
                    updated = true;
                }
            }
            if (!updated) break;
        }

        // 检查是否存在从起点可达的负环
        bool hasNegativeCycle = false;
        for (const Edge& e : edges) {
            if (dist[e.from] < INF && dist[e.to] > dist[e.from] + e.cost) {
                // 存在负环，并且从起点可达
                hasNegativeCycle = true;
                break;
            }
        }

        // 输出结果
        if (hasNegativeCycle) {
            cout << "Never
";
        } else if (dist[V - 1] == INF) {
            cout << "Impossible
";
        } else {
            cout << dist[V - 1] << "
";
        }
    }

    return 0;
}

总结

本题是一道经典的带负权边的最短路径问题，关键在于正确处理负权环的检测和特殊单元格的建模。 $Bellman-Ford$ 算法虽然效率不如 $Dijkstra$ ，但能够处理负权边并检测负环，非常适合本题。需要注意题目对负环的处理要求：只要存在从起点可达的负环，无论是否影响终点，都要报告 Never ，这是与标准最短路径问题的一个重要区别。

本文地址：https://www.vps345.com/25681.html

上一篇：AzerothCore容器化部署终极指南：从零构建专属M···

下一篇：AI大模型基座：分布式架构参数服务器与去中心化···

[2026-02-03]

Flutter for OpenHarmony 实战：Window···

[2026-02-03]

向日葵连接Ubuntu22.04黑屏

[2026-02-03]

安卓 Accessibility 服务在测试中的创新···

[2026-02-03]

基于IOT-Tree Server支持的gRPC服务，使···

[2026-02-03]

搭建PX4开发系统（Ubuntu 22.04)

[2026-02-03]

Flutter for OpenHarmony 实战：Window···

[2026-02-03]

向日葵连接Ubuntu22.04黑屏

[2026-02-03]

安卓 Accessibility 服务在测试中的创新···

[2026-02-03]

基于IOT-Tree Server支持的gRPC服务，使···

[2026-02-03]

搭建PX4开发系统（Ubuntu 22.04)

搜索文章

Tags