[SHOI2012] 回家的路

题意

有一个 n × n 的地铁网格，每个交点都是一个站。

走过相邻两个站，花 2 分钟
只有给出的 m 个换乘站，才能在站内从横线换到竖线，花 1 分钟

从学校 (sx, sy) 回家 (tx, ty)，问最少需要多少时间。
如果根本到不了，就输出 -1。

思路

先看一个最直接的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXV = MAXN * MAXN * 2 + 5;
const long long INF = (1LL << 60);

struct HeapNode {
    int u;
    long long dist;

    bool operator < (const HeapNode &other) const {
        return dist > other.dist;
    }
};

int n, m;
bool can_transfer[MAXN][MAXN];
int sx, sy, tx, ty;
vector<pair<int, int> > g[MAXV];
long long dist_arr[MAXV];
bool vis[MAXV];

int row_id(int x, int y) {
    return ((x - 1) * n + (y - 1)) * 2 + 1;
}

int col_id(int x, int y) {
    return ((x - 1) * n + (y - 1)) * 2 + 2;
}

void add_edge(int u, int v, int len) {
    g[u].push_back(make_pair(v, len));
}

void build_graph() {
    int tot = n * n * 2;
    for (int i = 1; i <= tot; i++) {
        g[i].clear();
    }

    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
            if (y + 1 <= n) {
                add_edge(row_id(x, y), row_id(x, y + 1), 2);
                add_edge(row_id(x, y + 1), row_id(x, y), 2);
            }
            if (x + 1 <= n) {
                add_edge(col_id(x, y), col_id(x + 1, y), 2);
                add_edge(col_id(x + 1, y), col_id(x, y), 2);
            }

            if (can_transfer[x][y]) {
                add_edge(row_id(x, y), col_id(x, y), 1);
                add_edge(col_id(x, y), row_id(x, y), 1);
            }
        }
    }
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            can_transfer[i][j] = false;
        }
    }

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        can_transfer[x][y] = true;
    }

    cin >> sx >> sy >> tx >> ty;

    build_graph();

    int tot = n * n * 2;
    for (int i = 1; i <= tot; i++) {
        dist_arr[i] = INF;
        vis[i] = false;
    }

    priority_queue<HeapNode> pq;
    dist_arr[row_id(sx, sy)] = 0;
    dist_arr[col_id(sx, sy)] = 0;
    pq.push({row_id(sx, sy), 0});
    pq.push({col_id(sx, sy), 0});

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.u;
        if (vis[u]) {
            continue;
        }
        vis[u] = true;

        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i].first;
            long long nd = dist_arr[u] + g[u][i].second;
            if (nd < dist_arr[v]) {
                dist_arr[v] = nd;
                pq.push({v, nd});
            }
        }
    }

    long long answer = min(dist_arr[row_id(tx, ty)], dist_arr[col_id(tx, ty)]);
    if (answer >= INF / 2) {
        cout << -1 << '\n';
    }
    else {
        cout << answer << '\n';
    }

    return 0;
}

brute.cpp 直接在整个 n × n 网格上建状态图：

每个站拆成两个状态：
- 正在坐横线
- 正在坐竖线
横线状态只能在同一行左右走
竖线状态只能在同一列上下走
如果这个站是换乘站，就在两个状态之间连一条权值 1 的边

这个做法最贴题意，但点数会膨胀到 2n^2。
本题 n 最大有 20000，显然不可能这样直接建。

关键观察是：

真正有决策意义的点，只有：
- 换乘站
- 起点
- 终点

因为在同一条横线或竖线上，如果中间一长串站都不能换乘，那么人只会“直着坐过去”，中间那些站不会产生新的选择。

所以我们只需要保留这些关键点。

1. 状态拆点

对于每个关键点 (x,y)，拆成两个点：

row(x,y)：表示你现在坐在横线里
col(x,y)：表示你现在坐在竖线里

如果这个关键点本身是换乘站，那么：

row(x,y) <-> col(x,y) 连一条权值 1 的边

这张图表示的就是这个拆点动作：

flowchart LR
  A["row(x,y)"] <-->|1| B["col(x,y)"]

这条边只在“能换乘”的站存在。
起点和终点就算和某个换乘站重合，我们也不额外发明规则，照样放进图里处理。

2. 同线只连相邻关键点

现在考虑同一行上的若干关键点。
如果它们按列坐标排好序是：

p1, p2, p3, ...

那么在横线状态里，只需要连：

p1 <-> p2
p2 <-> p3
…

边权就是站数差乘 2。

原因很简单：
在同一条线里直着坐，路费满足三角形关系。
如果你想从更左边去更右边，经过中间关键点拆成若干段，总代价和直接按站数计算是一样的。
所以只保留相邻关键点，就不会丢失最短路。

同一列完全同理。

样例结构图

这张图展示“关键点拆状态 + 同线相邻连边”的结构：

graph G {
  rankdir=LR;
  A [label="row(1,1)"];
  B [label="row(1,2)"];
  C [label="col(1,2)"];
  D [label="col(2,2)"];
  A -- B [label="2"];
  B -- C [label="1"];
  C -- D [label="2"];
}

它对应的正是：

先沿横线坐一站
在换乘站切到竖线
再沿竖线坐一站

这和题面的真实过程是一一对应的。

3. 起点和终点怎么处理

出发时你就在学校站里，所以：

可以直接选择先坐横线
也可以直接选择先坐竖线

都不需要额外换乘时间。
因此 Dijkstra 初始化时，把起点的两个状态距离都设成 0 即可。

终点同理，只要到达：

row(tx,ty) 或 col(tx,ty)

任意一个状态，都算到家了。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188#include <bits/stdc++.h>
using namespace std;

const int MAXP = 100000 + 5;
const int MAXV = MAXP * 2 + 10;
const int MAXE = 1200000 + 5;
const long long INF = (1LL << 60);

struct HeapNode {
    int u;
    long long dist;

    bool operator < (const HeapNode &other) const {
        return dist > other.dist;
    }
};

int n, m;
int px[MAXP], py[MAXP];
bool can_transfer[MAXP];
int point_cnt;
int sx, sy, tx, ty;

int head[MAXV], to[MAXE], nxt[MAXE], w[MAXE], edge_cnt;
long long dist_arr[MAXV];
bool vis[MAXV];

int row_order[MAXP], col_order[MAXP];

int row_id(int id) {
    return id * 2 - 1;
}

int col_id(int id) {
    return id * 2;
}

bool cmp_row(int a, int b) {
    if (px[a] != px[b]) {
        return px[a] < px[b];
    }
    if (py[a] != py[b]) {
        return py[a] < py[b];
    }
    return a < b;
}

bool cmp_col(int a, int b) {
    if (py[a] != py[b]) {
        return py[a] < py[b];
    }
    if (px[a] != px[b]) {
        return px[a] < px[b];
    }
    return a < b;
}

void init_graph() {
    edge_cnt = 0;
    for (int i = 1; i <= row_id(point_cnt) + 1; i++) {
        head[i] = 0;
    }
}

void add_edge(int u, int v, int len) {
    edge_cnt++;
    to[edge_cnt] = v;
    w[edge_cnt] = len;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void build_graph() {
    init_graph();

    // 换乘站可以在站内从横线切到竖线，代价 1。
    for (int i = 1; i <= m; i++) {
        add_edge(row_id(i), col_id(i), 1);
        add_edge(col_id(i), row_id(i), 1);
    }

    for (int i = 1; i <= point_cnt; i++) {
        row_order[i] = i;
        col_order[i] = i;
    }

    sort(row_order + 1, row_order + point_cnt + 1, cmp_row);
    sort(col_order + 1, col_order + point_cnt + 1, cmp_col);

    // 同一横线上的关键点，只需要连相邻的两个。
    for (int i = 2; i <= point_cnt; i++) {
        int a = row_order[i - 1];
        int b = row_order[i];
        if (px[a] != px[b]) {
            continue;
        }
        int len = (py[b] - py[a]) * 2;
        add_edge(row_id(a), row_id(b), len);
        add_edge(row_id(b), row_id(a), len);
    }

    // 同一竖线上的关键点，也只需要连相邻两个。
    for (int i = 2; i <= point_cnt; i++) {
        int a = col_order[i - 1];
        int b = col_order[i];
        if (py[a] != py[b]) {
            continue;
        }
        int len = (px[b] - px[a]) * 2;
        add_edge(col_id(a), col_id(b), len);
        add_edge(col_id(b), col_id(a), len);
    }
}

void dijkstra(int start_point) {
    int tot = point_cnt * 2;
    for (int i = 1; i <= tot; i++) {
        dist_arr[i] = INF;
        vis[i] = false;
    }

    priority_queue<HeapNode> pq;

    // 出发点可以直接选择坐横线或者竖线，不需要换乘时间。
    dist_arr[row_id(start_point)] = 0;
    dist_arr[col_id(start_point)] = 0;
    pq.push({row_id(start_point), 0});
    pq.push({col_id(start_point), 0});

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.u;
        if (vis[u]) {
            continue;
        }
        vis[u] = true;

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            long long nd = dist_arr[u] + w[i];
            if (nd < dist_arr[v]) {
                dist_arr[v] = nd;
                pq.push({v, nd});
            }
        }
    }
}

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

    cin >> n >> m;

    point_cnt = m;
    for (int i = 1; i <= m; i++) {
        cin >> px[i] >> py[i];
        can_transfer[i] = true;
    }

    cin >> sx >> sy >> tx >> ty;

    point_cnt++;
    px[point_cnt] = sx;
    py[point_cnt] = sy;
    int start_point = point_cnt;

    point_cnt++;
    px[point_cnt] = tx;
    py[point_cnt] = ty;
    int end_point = point_cnt;

    build_graph();
    dijkstra(start_point);

    long long answer = min(dist_arr[row_id(end_point)], dist_arr[col_id(end_point)]);

    if (answer >= INF / 2) {
        cout << -1 << '\n';
    }
    else {
        cout << answer << '\n';
    }

    return 0;
}

复杂度

设关键点总数是：

m + 2

排序两次：

$O(m log m)$

建图后的边数是线性的，因为每条横线、竖线只连相邻关键点。
最后跑一次 Dijkstra：

$O(m log m)$

总复杂度：

$O(m log m)$

空间复杂度：

$O(m)$

总结

这题最关键的不是最短路模板，而是先把大网格压缩掉。

真正有用的想法只有两步：

只保留“会产生选择”的关键点
每个关键点拆成横线状态和竖线状态

一旦建图想清楚，后面就是一题标准的最短路。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。