【题解】P7904 「DCOI」火烧の云

出题人题解。

D 火烧の云

Sol

考虑最短路，设一个三元组 \(dis(i,j,k)\) 表示到达位置 \((i,j)\) 且方向状态为 \(k\) 时所需最少步数。

初始化：所有点位置字符导致的连边、权值更新；\(dis(S_i,S_j,\{0,1,2,3\})=0\)，最终答案：\(\min\{dis(E_i,E_j,\{0,1,2,3\})\}\)。

注意多个起点多个终点的情况需要灵活地处理，考虑将所有起点和终点吊起来导向同一个虚拟根节点即可。

实现

设一个三元组

那么对于下面的这些字符：

除表格内的边，另外要连上

这些边就可以。Start 是超源，End 是超汇，跑一遍单源最短路 dis[Start]=0，最后 dis[End] 就是结果。

std

#include<queue>
#include<cstdio>
#include<cstring>
#define A mp(i, j, 0)
#define B mp(i, j, 1)
#define C mp(i, j, 2)
#define D mp(i, j, 3)
#define Start mp(n, m, 4)
#define End mp(n, m, 5)
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = 2005, M = 4000005, inf = 0x3f3f3f3f;
char ju[N][N]; bool vis[M << 2];
int n, m, a, b, c, d, head[M << 2], sLen, dis[M << 2];
int mp(int x, int y, int z){
	return (x < 1 || x > n || y < 1 || y > m) ? -1 : ((m * (x - 1) + y) << 2) + z;
}
struct Node{
	int next, to, value;
}s[M << 4];
inline void add(int u, int v, int w){
	if (u == -1 || v == -1) return;
	s[++sLen] = (Node){head[u], v, w};
	head[u] = sLen;
}
std::priority_queue<std::pair<int, int> >Q;
inline void dij(){
	memset(dis,0x3f,sizeof(dis));
	Q.push(std::make_pair(inf, Start)), dis[Start] = 0;
	while (!Q.empty()) {
		std::pair<int, int> tp = Q.top(); Q.pop();
		int u = tp.second;
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = head[u]; i; i = s[i].next) {
			int v = s[i].to, w = s[i].value;
			if (dis[u] + w < dis[v]) {
				dis[v] = dis[u] + w;
				if (!vis[v]) Q.push(std::make_pair(inf - dis[v], v));
			}
		}
	}
}
int main(){
	n = init(), m = init(), a = init(), b = init(), c = init(), d = init();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			while (ju[i][j] == '\0' || ju[i][j] == ' ' || ju[i][j] == '\n' || ju[i][j] == '\r') ju[i][j] = getchar();
			switch (ju[i][j]) {
				case '|': {
					add(A, mp(i + 1, j, 0), a), add(B, mp(i - 1, j, 2), a), add(B, mp(i + 1, j, 0), a), add(C, mp(i - 1, j, 2), a), add(D, mp(i - 1, j, 2), a), add(D, mp(i + 1, j, 0), a); break;
				}
				case '-': {
					add(A, mp(i, j - 1, 1), a), add(A, mp(i, j + 1, 3), a), add(B, mp(i, j - 1, 1), a), add(C, mp(i, j - 1, 1), a), add(C, mp(i, j + 1, 3), a), add(D, mp(i, j + 1, 3), a); break;
				}
				case '/': {
					add(A, mp(i, j - 1, 1), b), add(B, mp(i + 1, j, 0), b), add(C, mp(i, j + 1, 3), b), add(D, mp(i - 1, j, 2), b); break;
				}
				case '\\': {
					add(A, mp(i, j + 1, 3), b), add(B, mp(i - 1, j, 2), b), add(C, mp(i, j - 1, 1), b), add(D, mp(i + 1, j, 0), b); break;
				}
				case '.': {
					add(A, mp(i + 1, j, 0), c), add(A, mp(i, j - 1, 1), c), add(A, mp(i - 1, j, 2), c), add(A, mp(i, j + 1, 3), c), add(B, mp(i + 1, j, 0), c), add(B, mp(i, j - 1, 1), c), add(B, mp(i - 1, j, 2), c), add(B, mp(i, j + 1, 3), c), add(C, mp(i + 1, j, 0), c), add(C, mp(i, j - 1, 1), c), add(C, mp(i - 1, j, 2), c), add(C, mp(i, j + 1, 3), c), add(D, mp(i + 1, j, 0), c), add(D, mp(i, j - 1, 1), c), add(D, mp(i - 1, j, 2), c), add(D, mp(i, j + 1, 3), c); break;
				}
				case '<': {
					add(A, mp(i, j - 1, 1), d), add(B, mp(i, j - 2, 1), 0), add(C, mp(i, j - 1, 1), d); break;
				}
				case '>': {
					add(A, mp(i, j + 1, 3), d), add(C, mp(i, j + 1, 3), d), add(D, mp(i, j + 2, 3), 0); break;
				}
				case '^': {
					add(B, mp(i - 1, j, 2), d), add(C, mp(i - 2, j, 2), 0), add(D, mp(i - 1, j, 2), d); break;
				}
				case 'v': {
					add(A, mp(i + 2, j, 0), 0), add(B, mp(i + 1, j, 0), d), add(D, mp(i + 1, j, 0), d); break;
				}
				case 'S': {
					add(Start, A, 0), add(Start, B, 0), add(Start, C, 0), add(Start, D, 0), add(A, mp(i + 1, j, 0), 0), add(A, mp(i, j - 1, 1), 0), add(A, mp(i - 1, j, 2), 0), add(A, mp(i, j + 1, 3), 0), add(B, mp(i + 1, j, 0), 0), add(B, mp(i, j - 1, 1), 0), add(B, mp(i - 1, j, 2), 0), add(B, mp(i, j + 1, 3), 0), add(C, mp(i + 1, j, 0), 0), add(C, mp(i, j - 1, 1), 0), add(C, mp(i - 1, j, 2), 0), add(C, mp(i, j + 1, 3), 0), add(D, mp(i + 1, j, 0), 0), add(D, mp(i, j - 1, 1), 0), add(D, mp(i - 1, j, 2), 0), add(D, mp(i, j + 1, 3), 0); break;
				}
				case 'E': {
					add(A, End, 0), add(B, End, 0), add(C, End, 0), add(D, End, 0); break;
				}
			}
		}
	dij();
	print(dis[End] == inf ? -1 : dis[End]), putchar('\n');
}