NOIp2018模拟赛 Maze

二分答案 最短路

题面

有一个 n*m 的迷宫,这个迷宫由 n 行 m 列 0 或 1 组成,0 表示可以走,1 表示不能走。
你从起点出发,每次可以向上下左右四个方向走一格,走一格用时 1 秒。
你有一个机器,使得每次在上下移动一步时,用时为 k 秒。
你需要选定一个 k,使得从起点到终点的最短用时等于 s。

我考场上竟然没有写挂，感动

发现最短用时是随着 k 递增的，遂二分 k

然后最短路判断一下就行啦

#include <bits/stdc++.h>
const double EPS = 1e-5;
const int INF = 0x3f3f3f3f;
const int MAXN = 100;
const int NXT[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n, m, sx, sy, ex, ey;
int g[MAXN + 5][MAXN + 5];
double s;
double dist[MAXN + 5][MAXN + 5];
struct Heap {
    int x, y;
    double d;
    Heap(){}
    Heap(int xx, int yy, double dd) {
        x = xx;
        y = yy;
        d = dd;
    }
};
bool operator < (const Heap &a, const Heap &b) {
    return a.d > b.d;
}
inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
bool check(double x) {
    std::priority_queue <Heap> q;
    while(!q.empty()) q.pop();
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) dist[i][j] = INF;
    dist[sx][sy] = 0;
    q.push(Heap(sx, sy, 0));
    while(!q.empty()) {
        Heap from = q.top();
        q.pop();
        if(from.x == ex && from.y == ey) break;
        if(from.d != dist[from.x][from.y]) continue;
        for(int k = 0; k < 4; ++k) {
            int tx = from.x + NXT[k][0], ty = from.y + NXT[k][1];
            double w = (k > 1) ? x : 1;
            if(g[tx][ty] > 0) continue;
            if(dist[tx][ty] > dist[from.x][from.y] + w) {
                dist[tx][ty] = dist[from.x][from.y] + w;
                q.push(Heap(tx, ty, dist[tx][ty]));
            }
        }
    }
    return dist[ex][ey] <= s;
}
int main() {
    n = read();
    m = read();
    sx = read();
    sy = read();
    ex = read();
    ey = read();
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) g[i][j] = read();
    scanf("%lf", &s);
    double ans = 0, l = 0, r = s, mid;
    while(l + EPS <= r) {
        mid = (l + r) / 2;
        if(check(mid)) {
            l = mid;
            ans = mid;
        }
        else r = mid;
    }
    printf("%.3lf", ans);
    return 0;
}