A41137.迷宫

LingKerly

2025-03-15 21:48:06

发布于：重庆

25阅读

0回复

0点赞

注意到可以最小生成树来解决本问题。如果连接了头和屁股，此时用的边一定是最短的那一些，此时最大的边就是答案。

有帮助，赞一个

去预览

0/2000

全部评论 2

LingKerly

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define int long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,k; cin >> n >> m >> k;
    vector<pair<int,int>> d(k + 2);
    for(int i = 0 ; i < k ; i ++) {
        int x,y; cin >> x >> y;
        d[i] = {x,y};
    } d[k + 1].se = m;

    auto dis = [&](int x , int y) -> long long{
        if(x == k) return d[y].se * d[y].se;
        if(y == k) return d[x].se * d[x].se;
        if(x == k + 1) return (m - d[y].se) * (m - d[y].se);
        if(y == k + 1) return (m - d[x].se) * (m - d[x].se);
        return (long long)(d[x].fi - d[y].fi) * (d[x].fi - d[y].fi) + (long long)(d[x].se - d[y].se) * (d[x].se - d[y].se);
    };

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    q.emplace(0,k);
    bitset<6010> st;
    vector<int> f(k + 2,1e18); f[k] = 0;
    int ans = 0;
    while(q.size()) {
        auto [d,u] = q.top(); q.pop();
        if(st[u]) continue; 
        st[u] = true;
        ans=max(ans,d);
        if(u==k+1)break;//crucial
        for(int i = 0 ; i < k + 2 ; i ++) 
            if(i != u){
                if(f[i] > dis(u,i)) {
                    f[i] = dis(u,i); 
                    q.emplace(f[i],i);
                }
        }
    }
    cout << fixed << setprecision(6) << sqrtl(ans) / 2. << "\n";
    return 0;
}

2025-03-16 来自重庆

LingKerly

二分+bfs：

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma optimize(3, on)
#pragma GCC optimize("Ofast")

// #include<ext/pb_ds/priority_queue.hpp>
// #include<ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

// #define int long long
#define fi first
#define se second

template <typename T>
inline void read(T &x) {
    T f = 1;
    x = 0;
    char ch = getchar();
    while (0 == isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (0 != isdigit(ch))
        x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    x *= f;
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        x = ~(x - 1);
        putchar('-');
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

int q[6010];
bitset<6010> st;

signed main() {
    int n,m,k;;
    read(n) , read(m) , read(k);
    vector<pair<int,int>> d(k);
    for(int i = 0 ; i < k ; ++ i) {
        int x,y; read(x) , read(y);
        d[i] = {x,y};
    }
    auto dis = [&](int x , int y) -> long long{
        return (long long)(d[x].fi - d[y].fi) * (d[x].fi - d[y].fi) + (long long)(d[x].se - d[y].se) * (d[x].se - d[y].se);
    };
    auto check = [&](double &ans) {
        if (ans >= m) return true;
        int hh = 0 , tt = -1;
        for(int i = 0 ; i < k ; ++ i) if(d[i].se < ans) {
            q[++tt] = i , st[i] = 1;
        } else st[i] = 0;
        while(hh <= tt) {
            int u = q[hh++];
            if(d[u].se + ans >= m) return true;
            for(int i = 0 ; i < k ; ++ i) {
                if(dis(i,u) > ans * ans || st[i]) continue;
                st[i] = 1; q[++tt] = i;
            }
        }
        return false;
    };
    double lo = 0 , ro = 3e5 + 1;
    while(ro - lo >= 7e-6) {
        double mid = (lo + ro) / 2;
        if(check(mid)) ro = mid;
        else lo = mid;
    }
    // cout << fixed << setprecision(10) << lo / 2. << "\n";
    printf("%.8lf",lo/2.);
    return 0;
}

2025-03-16 来自重庆