Kuangbin 最短路+二分青蛙（小坑）

素颜马尾好姑娘i 2024-03-30 11:44 38阅读 0赞

[4240. 青蛙 - AcWing题库][4240. _ - AcWing]

题意：

![2333daa0820c4da5a44633d4ff84448e.png][]**思路：**

**求最大值最小，二分答案就行，去二分最长边**

**在check函数里面建图，把所有长度小于最长边的边都连上，然后去跑最短路，看能不能跑通**

**易错点：**

**1.二分答案和dist数组都要变成double类型**

**2.二分答案精度统一设成1e-6**

**3.dist初始化成无穷大应该初始化成1e9+7而不是0x3f3f3f3f，0x3f只是针对整数来说的**

**4.要重新建图别忘了初始化tot和head数组**

**5.vis\[s\]不需要初始化为1**

**6.建无向边，add两次**

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e2+10,mxe=4e4+10;
    const double eps=1e-6,mnf=1e9+7;
    struct ty{
        int x,y;
    }a[mxn];
    struct ty2{
        int to,next;
        double w;
    }edge[mxe<<1];
    struct ty3{
        int x;
        double dis;
        bool operator<(const ty3&a) const{
            return a.dis<dis;
        }
    };
    queue<ty3> q;
    int n,tot=0,T=0;
    int head[mxn],vis[mxn];
    double dis[mxn];
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
        }
        while(!q.empty()) q.pop();
    }
    void init2(){
        tot=0;
        for(int i=0;i<=n;i++) head[i]=-1;
    }
    void add(int u,int v,double w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    double dist(int a1,int b1,int a2,int b2){
        return sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));
    }
    bool dij(int s,int t){
        //memset(dis,0x3f,sizeof(dis));
        for(int i=0;i<=n;i++) dis[i]=mnf;
        memset(vis,0,sizeof(vis));
        dis[s]=0;q.push({s,0});
        while(!q.empty()){
            ty3 u=q.front();
            q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                if(vis[edge[i].to]) continue;
                if(dis[edge[i].to]>dis[u.x]+edge[i].w){
                    dis[edge[i].to]=dis[u.x]+edge[i].w;
                    q.push({edge[i].to,dis[edge[i].to]});
                }
            }
        }
        return (dis[t]!=mnf);
    }
    bool check(double x){
        init2();
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(dist(a[i].x,a[i].y,a[j].x,a[j].y)<=x) add(i,j,dist(a[i].x,a[i].y,a[j].x,a[j].y)),add(j,i,dist(a[i].x,a[i].y,a[j].x,a[j].y));
            }
        }
        return dij(1,2);
    }
    void solve(){
        while(cin>>n&&n!=0){
            cout<<"Scenario #"<<++T<<'\n';
            init();
            for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
            double l=0,r=1415.0;
            while(r-l>eps){
                double mid=(l+r)/2;
                if(check(mid)) r=mid;
                else l=mid;
            }
            cout<<"Frog Distance = "<<fixed<<setprecision(3)<<r<<'\n';
            cout<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int _=1;//cin>>_;
        while(_--)solve();return 0;
    }

[4240. _ - AcWing]: https://www.acwing.com/problem/content/4243/
[2333daa0820c4da5a44633d4ff84448e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/37acf7836829427ea36bd6d6b0055af0.png