AT_arc008_3 题解

ikunTLE · 2024-12-19 22:14:37 · 题解

题目传送门

思路

不难想到可以用最短路解决此题。

本题中可以将每个人当作一个点，将两个人传递小丸子所需时间建成边权，做最短路即可。

由于 N\le10^3，考虑 Floyd，时间复杂度 \mathcal{O}(N^3)，可以通过此题。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e3+10;
int x[N],y[N],t[N],r[N];
double f[N][N];
int main(){
    int n=read();
    for(int i=1;i<=n;++i)
        x[i]=read(),y[i]=read(),t[i]=read(),r[i]=read();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            f[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))/min(t[i],r[j]);
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    sort(f[1]+1,f[1]+n+1);
    double ans=0;
    for(int i=2;i<=n;++i)
        ans=max(ans,f[1][i]+n-i);
    printf("%.12lf\n",ans);
    return 0;
}