「Bzoj 1295」「SCOI2009」最长距离 (最短路)

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

#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;
}