题解 P3632 【[APIO2011]寻路】
打了一中午。。。
感觉自己打的是纯暴力
首先离散化，重新给所有点标上坐标
对于蜂巢边缘的每一个点，向他四周最近的点（蜂巢边缘的点）连边
然后是起点终点连边
然后跑最短路，就做完了，主要是细节问题，模拟建图，很耗时间
下面是我又臭又长的代码
#include <bits/stdc++.h>
#define jh(x,y) x^=y^=x^=y
#define loc(x,y) (x-1)*totl+y
using namespace std;
const int N = 2e3 + 10;
inline int read()
{
register int num = 0;
register char ch;
register bool flag = false;
while ((ch = getchar()) == ' ' || ch == '\n' || ch == '\r');
if (ch == '-')flag = true; else num = ch ^ 48;
while ((ch = getchar()) != ' '&&ch != '\n'&&ch != '\r'&&~ch)
num = (num << 1) + (num << 3) + (ch ^ 48);
if (flag)return -num; return num;
}
int sx, sy, ex, ey, hang[10 * N], lie[10 * N], toth, totl;
struct Node {
int x1, y1, x2, y2;
inline Node() { x1 = y1 = x2 = y2 = 0; }
inline Node(register int a, register int b, register int c, register int d) { x1 = a, y1 = b, x2 = c, y2 = d; }
}fc[N];
inline void change(register int &x, register int &y)
{
x = lower_bound(hang + 1, hang + toth + 1, x) - hang;
y = lower_bound(lie + 1, lie + totl + 1, y) - lie;
}
bool in[N][N];
int mp[N][N], nt[N*N], b[N*N], p[N*N], w[N*N], num;
inline void add(register int x, register int y, register int z)
{
if (z == 0)return;
b[++num] = y; w[num] = z;
nt[num] = p[x]; p[x] = num;
b[++num] = x; w[num] = z;
nt[num] = p[y]; p[y] = num;
}
inline void update(register int x, register int y)
{
for (register int i = x + 1; i <= toth; ++i)
if (mp[i][y])
{
if (mp[i][y] == mp[x][y] && y != fc[mp[x][y]].y1&&y != fc[mp[x][y]].y2)break;
add(loc(x, y), loc(i, y), hang[i] - hang[x]);
break;
}
for (register int i = y + 1; i <= totl; ++i)
if (mp[x][i])
{
if (mp[x][i] == mp[x][y] && x != fc[mp[x][y]].x1&&x != fc[mp[x][y]].x2)break;
add(loc(x, y), loc(x, i), lie[i] - lie[y]);
break;
}
}
inline void ud(register int x, register int y)
{
for (register int i = x + 1; i <= toth; ++i)if (mp[i][y]) { add(loc(x, y), loc(i, y), hang[i] - hang[x]); break; }
for (register int i = x - 1; i >= 1; --i)if (mp[i][y]) { add(loc(x, y), loc(i, y), hang[x] - hang[i]); break; }
for (register int i = y + 1; i <= totl; ++i)if (mp[x][i]) { add(loc(x, y), loc(x, i), lie[i] - lie[y]); break; }
for (register int i = y - 1; i >= 1; --i)if (mp[x][i]) { add(loc(x, y), loc(x, i), lie[y] - lie[i]); break; }
}
int dist[N*N], top;
bool flag[N*N];
struct node {
int bh, dist;
inline node() { bh = dist = 0; }
inline node(register int a, register int b) { bh = a, dist = b; }
}q[N*N];
inline void shift()
{
register int i = 1, j = 2;
while (j <= top)
{
if (j < top&&q[j + 1].dist < q[j].dist)++j;
if (q[i].dist > q[j].dist)
jh(q[i].bh, q[j].bh), jh(q[i].dist, q[j].dist);
i = j, j = i << 1;
}
}
inline void shift2()
{
register int i = top, j = top >> 1;
while (i > 1)
{
if (q[i].dist >= q[j].dist)break;
jh(q[i].bh, q[j].bh);
jh(q[i].dist, q[j].dist);
i = j, j = i >> 1;
}
}
inline int dijkstra(register int x)
{
memset(dist, 63, sizeof(dist));
memset(flag, 0, sizeof(flag));
q[top = 1] = node(x, dist[x] = 0);
while (top)
{
register node k = q[1]; q[1] = q[top--]; shift();
if (!flag[k.bh])
{
flag[k.bh] = true;
register int e = p[k.bh];
while (e)
{
register int kk = b[e];
if (dist[kk] - w[e] > dist[k.bh])
dist[kk] = dist[k.bh] + w[e];
q[++top] = node(kk, dist[kk]); shift2();
e = nt[e];
}
}
}
return dist[loc(ex, ey)];
}
int main()
{
register int t = read();
while (t--)
{
num = 0, toth = totl = 0; memset(p, 0, sizeof(p));
memset(mp, 0, sizeof(mp)); memset(in, 0, sizeof(in));
hang[++toth] = sx = read(), lie[++totl] = sy = read();
hang[++toth] = ex = read(), lie[++totl] = ey = read();
register int n = read();
for (register int i = 1; i <= n; ++i)
{
register int x1 = read(), y1 = read(), x2 = read(), y2 = read();
if (x1 > x2)jh(x1, x2);
if (y1 > y2)jh(y1, y2);
hang[++toth] = x1, hang[++toth] = x2;
lie[++totl] = y1, lie[++totl] = y2;
fc[i] = Node(x1, y1, x2, y2);
}
sort(hang + 1, hang + toth + 1);
sort(lie + 1, lie + totl + 1);
toth = unique(hang + 1, hang + toth + 1) - hang - 1;
totl = unique(lie + 1, lie + totl + 1) - lie - 1;
change(sx, sy); change(ex, ey);
for (register int i = 1; i <= n; ++i)
change(fc[i].x1, fc[i].y1),
change(fc[i].x2, fc[i].y2);
for (register int i = 1; i <= n; ++i)
for (register int x = fc[i].x1; x <= fc[i].x2; ++x)
for (register int y = fc[i].y1; y <= fc[i].y2; ++y)
mp[x][y] = i;
for (register int i = 1; i <= n; ++i)
{
for (register int x = fc[i].x1 + 1; x < fc[i].x2; ++x)update(x, fc[i].y1), update(x, fc[i].y2);
for (register int y = fc[i].y1; y <= fc[i].y2; ++y)update(fc[i].x1, y), update(fc[i].x2, y);
}
mp[sx][sy] = mp[ex][ey] = 1;
ud(sx, sy); ud(ex, ey);
register int ans = dijkstra(loc(sx, sy));
if (ans < 1e9)printf("%d\n", ans);
else printf("No Path\n");
}
return 0;
}