「JOI 2013 Final」现代豪宅 题解

题目大意

有一个 $M \times N$ 的网格豪宅，初始状态：

• 南北方向的门打开（可以通行）
• 东西方向的门关闭（不可通行）

一些房间中有开关，按住开关1分钟会翻转所有门的状态（打开的关闭，关闭的打开）。

求从 $(1,1)$ 到 $(M,N)$ 的最短时间，如果无法到达输出 $-1$。

核心思路

状态分析

由于开关影响所有门，整个豪宅只有两种状态：

• 状态0：南北通，东西不通
• 状态1：南北不通，东西通

关键观察

1. 只有在有开关的房间才能改变移动方向
2. 路径必然经过若干有开关的房间
3. 对于 $M,N \leq 10^5$ 的数据范围，不能直接建网格图

算法设计

分层图建模

为每个有开关的房间创建两个节点：

• 垂直节点 $(2i-1)$：到达时处于状态0（可南北移动）
• 水平节点 $(2i)$：到达时处于状态1（可东西移动）

建图策略

1. 状态切换边

在同一房间内切换状态需要1分钟：

垂直节点 ↔ 水平节点, 权重 = 1

2. 垂直移动边

同列的房间间，如果都处于状态0，可以南北移动：

垂直节点 ↔ 垂直节点, 权重 = |y₂ - y₁|

3. 水平移动边

同行的房间间，如果都处于状态1，可以东西移动：

水平节点 ↔ 水平节点, 权重 = |x₂ - x₁|

最短路计算

初始化

从起点 $(1,1)$ 出发：

• 如果第一列有开关房间 $(1,y)$，初始距离为 $y-1$（南北移动时间）
• 初始状态为状态0（垂直节点）

终止条件

到达终点 $(M,N)$：

• 从垂直节点出发到最后一列：$dis + (N-y)$
• 从水平节点出发到最后一行：$dis + (M-x)$

代码实现

#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;

struct point {
    int x, y, id;
};

struct node {
    int u;
    long long d;
    bool operator<(const node &b) const {
        return d > b.d;
    }
};

int main() {
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);
    vector<point> a(k);
    int idx = 0;

    // 读入所有开关房间
    for (auto &[x, y, id] : a) {
        scanf("%d %d", &x, &y);
        id = (++idx);
    }

    int tot = 2 * k;  // 总节点数
    vector<vector<pair<int, int>>> e(tot + 1);
    
    // 按列排序，建垂直边
    sort(a.begin(), a.end(), [&](const point &p1, const point &p2) {
        return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
    });

    for (int i = 1; i < k; i++) {
        if (a[i - 1].x == a[i].x) {
            int u = 2 * a[i - 1].id - 1, v = 2 * a[i].id - 1;
            int w = a[i].y - a[i - 1].y;
            e[u].push_back({v, w});
            e[v].push_back({u, w});
        }
    }

    // 按行排序，建水平边
    sort(a.begin(), a.end(), [&](const point &p1, const point &p2) {
        return p1.y == p2.y ? p1.x < p2.x : p1.y < p2.y;
    });

    for (int i = 1; i < k; i++) {
        if (a[i - 1].y == a[i].y) {
            int u = 2 * a[i - 1].id, v = 2 * a[i].id;
            int w = a[i].x - a[i - 1].x;
            e[u].push_back({v, w});
            e[v].push_back({u, w});
        }
    }

    // 同一房间的状态切换边
    for (int i = 0; i < k; i++) {
        int u = 2 * a[i].id - 1, v = 2 * a[i].id;
        e[u].push_back({v, 1});
        e[v].push_back({u, 1});
    }

    // Dijkstra最短路
    vector<long long> dis(tot + 1, inf);
    vector<bool> vis(tot + 1, false);
    priority_queue<node> Q;

    // 初始化：从第一列的开关房间开始
    for (int i = 0; i < k; i++) {
        if (a[i].x == 1) {
            int u = 2 * a[i].id - 1;  // 垂直状态
            dis[u] = a[i].y - 1;      // 从(1,1)南北移动到此房间
            Q.push({u, dis[u]});
        }
    }

    while (!Q.empty()) {
        auto [u, d] = Q.top();
        Q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        
        for (auto [to, w] : e[u]) {
            if (dis[to] > d + w) {
                dis[to] = d + w;
                Q.push({to, dis[to]});
            }
        }
    }

    // 计算到达终点的最短时间
    long long ans = inf;
    for (int i = 0; i < k; i++) {
        // 从垂直节点出发到最后一列
        if (a[i].x == m) {
            ans = min(ans, dis[2 * a[i].id - 1] + n - a[i].y);
        }
        // 从水平节点出发到最后一行  
        if (a[i].y == n) {
            ans = min(ans, dis[2 * a[i].id] + m - a[i].x);
        }
    }

    if (ans == inf) ans = -1;
    printf("%lld\n", ans);
    return 0;
}

复杂度分析

• 建图：$O(K \log K)$（排序）
• 最短路：$O(K \log K)$（Dijkstra在 $2K$ 个节点上）
• 总复杂度：$O(K \log K)$

样例分析

样例1：

M=3, N=2, K=1
开关：(1,2)

路径：$(1,1) \xrightarrow{1} (1,2) \xrightarrow{1} \text{切换状态} \xrightarrow{1} (2,2) \xrightarrow{1} (3,2)$
总时间：$1 + 1 + 1 + 1 = 4$

样例2：

M=3, N=2, K=1  
开关：(2,1)

无法到达终点，输出 $-1$