[JOI 2013 Final]现代豪宅

[JOI 2013 Final]现代豪宅

题意

给出一个 \(n\times m\) 的网格图，每两个格子之间有一扇门。

初始上下方向的门都是开着的，左右方向的门是关着的。

有一些格子有按钮，可以把打开的门关上，关上的门打开。

走一步需要一秒，按按钮需要一秒，求从 \((1,1)\) 到达 \((n,m)\) 的最小步数。

思路

发现题意等价于只能在按钮处拐弯。

只用把起点，终点还有每个按钮建立成点，连边跑最短路。

同一行同一列的点只用相邻的连边，边权为两点距离。

起点只用和第一列的第一个按钮连边，边权同理。

终点只用和最后一列最后一个按钮和最后一行最后一个按钮连边，边权同理。

那按按钮需要花费一秒，我们需要在按钮内部建出一条边权为 \(1\) 的点，怎么办呢？

把一个按钮拆成 \(3\) 个点，分别问行出入口，列出入口，中转站。

行出入口向中转站连一条边权为 \(1\) 的边，

列出入口向中转站连一条边权为 \(1\) 的边，

中转站向行出入口和列出入口连边权为 \(0\) 的边。

（可以想象成坐地铁，进站要给钱，出站不用）

同一列的点列出入口相互连接，

同一行的点行出入口相互连接。

这样就与题目的网格图等价，跑最短路就行了。

代码

#include <bits/stdc++.h>
#define MIDDLE 0
#define LEFT_RIGHT 1
#define UP_DOWN 2
#define S_T 4
using namespace std;

const int N = 2e6 + 5;
using LL = long long;

int tot, head[N], ver[N * 2], nxt[N * 2];
LL edge[N * 2], dis[N];

map <pair <int, pair<int, int>>, int> id;
vector <int> h[N], l[N];

int n, m, k, cnt;
struct Button {
	int x, y;
};
Button b[N];

struct node {
	int id; LL dis;
};

bool operator < (node x, node y) {
	return x.dis > y.dis;
}

priority_queue <node> Q;
bool vis[N];

void add(int x, int y, LL z) {
	ver[++ tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
	edge[tot] = z;
}

int get_id(int x, int y, int t) {
	if (id.find({x, {y, t}}) != id.end())
		return id[{x, {y, t}}];
	id[{x, {y, t}}] = ++ cnt;
	return cnt;
}

void dijkstra(int s) {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	Q.push({s, 0});
	while (!Q.empty()) {
		int x = Q.top().id; Q.pop();
		if (vis[x]) continue;
		vis[x] = 1;
		for (int i = head[x], y; i; i = nxt[i]) {
			y = ver[i];
			if (dis[y] > dis[x] + edge[i]) {
				dis[y] = dis[x] + edge[i];
				Q.push({y, dis[y]});
			}
		}
	}
}

int main() {
	freopen("house.in", "r", stdin);
	freopen("house.out", "w", stdout); 
	
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> m >> n >> k;
	
	int S = get_id(1, 1, S_T), T = get_id(m, n, S_T);
	
	for (int i = 1; i <= k; i ++) {
		cin >> b[i].y >> b[i].x;
		h[b[i].x].push_back(b[i].y);
		l[b[i].y].push_back(b[i].x);
		int x = get_id(b[i].x, b[i].y, MIDDLE);
		int y = get_id(b[i].x, b[i].y, LEFT_RIGHT);
		int z = get_id(b[i].x, b[i].y, UP_DOWN);
		add(y, x, 1); add(x, y, 0);
		add(z, x, 1); add(x, z, 0);
	}
	
	for (int i = 1; i <= n; i ++) {
		if (!h[i].size()) continue;
		sort(h[i].begin(), h[i].end());
		for (size_t j = 0; j < h[i].size() - 1; j ++) {
			int x = get_id(i, h[i][j], LEFT_RIGHT);
			int y = get_id(i, h[i][j + 1], LEFT_RIGHT);
			add(x, y, h[i][j + 1] - h[i][j]);
			add(y, x, h[i][j + 1] - h[i][j]);
		}
	}
	
	for (int i = 1; i <= m; i ++) {
		if (!l[i].size()) continue;
		sort(l[i].begin(), l[i].end());
		for (size_t j = 0; j < l[i].size() - 1; j ++) {
			int x = get_id(l[i][j], i, UP_DOWN);
			int y = get_id(l[i][j + 1], i, UP_DOWN);
			add(x, y, l[i][j + 1] - l[i][j]);
			add(y, x, l[i][j + 1] - l[i][j]);
		}
	}
	
	if (l[1].size()) {
		int temp = get_id(l[1][0], 1, UP_DOWN);
		add(S, temp, l[1][0] - 1);
		add(temp, S, l[1][0] - 1);
	}
	
	
	if (h[n].size()) {
		int temp = get_id(n, h[n].back(), LEFT_RIGHT);
		add(T, temp, m - h[n].back());
		add(temp, T, m - h[n].back());
	}
	
	if (l[m].size()) {
		int temp = get_id(l[m].back(), m, UP_DOWN);
		add(T, temp, n - l[m].back());
		add(temp, T, n - l[m].back());
	}
	
	dijkstra(S);
	
	if (dis[T] ==	dis[0]) cout << -1 << "\n";
	else cout << dis[T] << "\n";
	return 0;
}