[SCOI]最长距离

题目大意

给你一个图，里面有障碍
你能移走个障碍，然后求能够联通的一个点对的最大距离是多少

分析

因为求的只是一个点对的最大距离，所以其实我们只需要一走这一条路径上的障碍即可

那么只要路径上的最小障碍数量小于等于就可以更细答案

求路径上的障碍数可以用最短路的思想，把点权看作边权即可

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 50 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int n, m, t, ans;
int dis[maxn][maxn], cost[maxn][maxn];
bool vis[maxn][maxn];
const int mx[] = {1, -1, 0, 0};
const int my[] = {0, 0, 1, -1};

struct Node
{
    int x, y;
    Node () {}
    Node (int x, int y) : x(x), y(y) {}
    bool operator < (const Node &T) const {
        return dis[x][y] > dis[T.x][T.y];
    }
};

void BFS(int fx, int fy)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    priority_queue <Node> Q;
    dis[fx][fy] = cost[fx][fy];
    Q.push(Node(fx, fy));
    while (!Q.empty()) {
        Node Now = Q.top();
        Q.pop();
        if (vis[Now.x][Now.y]) continue;
        if (dis[Now.x][Now.y] <= t) {
            ans = max(ans, (fx - Now.x) * (fx - Now.x) + (fy - Now.y) * (fy - Now.y));
        } else continue;
        vis[Now.x][Now.y] = 1;
        for (int i(0); i < 4; ++i) {
            int nx = mx[i] + Now.x;
            int ny = my[i] + Now.y;
            if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny]) continue;
            if (dis[nx][ny] <= cost[Now.x][Now.y] + cost[nx][ny]) continue;
            dis[nx][ny] = cost[Now.x][Now.y] + cost[nx][ny];
            Q.push(Node(nx, ny));
        }
    }
}

signed main()
{
    n = __read(), m = __read(), t = __read();
    for (int i = 1; i <= n; ++i) {
        char opt[maxn];
        scanf ("%s", opt + 1);
        for (int j = 1; j <= m; ++j)
            cost[i][j] = opt[j] - '0';
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            BFS(i, j);

    printf ("%.6f\n", sqrt(ans));
    system("pause");
}