Bzoj 1295(最短路)

BZOJ 1295
逆向思维,设$g(i,j)$为$i$到$j$最少穿过的障碍物。每个点做一次SPFA。
然后之后枚举点对,如果$g(i,j)<=T$,那么就统计答案。
这里代码使用了点标号,比较麻烦,看题解似乎可以直接BFS,就不用连边了。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 30 + 5, INF = 1000000000;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
struct data {
int v, w;
}e[MAXN * MAXN * 8];
int en, n, m, T, dis[MAXN * MAXN][MAXN * MAXN], vi[MAXN * MAXN];
char s[MAXN][MAXN];
vector<int> G[MAXN * MAXN];
void ins(int x, int y, int c) {
en++, e[en].v = y, e[en].w = c, G[x].push_back(en);
}
int getIDbyPos(int x, int y) {
return (x - 1) * m + y;
}
void getPosbyID(int x, int &a, int &b) {
if (x % m == 0) a = x / m; else a = x / m + 1;
b = x - m * (a - 1);
}
db dist(int x, int y, int i, int j) {
return (x - i) * (x - i) + (y - j) * (y - j);
}
void spfa(int x) {
queue<int> q;
int xx, xy; getPosbyID(x, xx, xy);
ms(vi, false), dis[x][x] = s[xx][xy] - '0', vi[x] = true, q.push(x);
while (!q.empty()) {
int u = q.front(); q.pop(), vi[u] = false;
for (int i=0;i<G[u].size();i++) {
int v = e[G[u][i]].v, w = e[G[u][i]].w;
if (dis[x][v] > dis[x][u] + w) {
dis[x][v] = dis[x][u] + w;
if (!vi[v]) vi[v] = true, q.push(v);
}
}
}
}
void clean() {
en = 0;
for (int i=0;i<=n*n;i++) {
G[i].clear();
for (int j=0;j<=n*n;j++) dis[i][j] = INF;
}
}
void solve() {
clean();
for (int i=1;i<=n;i++) scanf("%s", s[i] + 1);
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
int nowID = getIDbyPos(i, j);
for (int orz=0;orz<4;orz++) {
int tx = i + dx[orz], ty = j + dy[orz];
if (tx > 0 && ty > 0 && tx <= n && ty <= m) {
int curID = getIDbyPos(tx, ty);
if (s[i][j] == '0' && s[tx][ty] == '0') ins(nowID, curID, 0), ins(curID, nowID, 0);
if (s[i][j] == '1' && s[tx][ty] == '1') ins(nowID, curID, 1), ins(curID, nowID, 1);
if (s[i][j] == '0' && s[tx][ty] == '1') ins(nowID, curID, 1), ins(curID, nowID, 0);
if (s[i][j] == '1' && s[tx][ty] == '0') ins(nowID, curID, 0), ins(curID, nowID, 1);
}
}
}
}
for (int i=1;i<=n*n;i++) spfa(i);
db ans = 0;
for (int i=1;i<=n*n;i++) {
for (int j=1;j<=n*n;j++) {
if (dis[i][j] > T) continue;
int ix, iy, jx, jy;
getPosbyID(i, ix, iy), getPosbyID(j, jx, jy);
ans = max(ans, dist(ix, iy, jx, jy));
}
}
printf("%.6f\n", sqrt(ans));
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d%d", &n ,&m, &T), solve();
return 0;
}
------ 本文结束 ------