G - Easy Glide

SDUT 2022 Spring Team Contest(for 21) - 12 - Virtual Judge

 

Grammy is playing a boring racing game named Easy Gliding. The game's main content is to reach the destination as fast as possible by walking or gliding. The fastest player wins.

Each player controls a character on a two-dimensional plane. A character can walk at any moment with a speed of V_1V1​. Especially, when a character touches a gliding point, he/she can glide with a speed of V_2V2​ for the following 33 seconds. It is guaranteed that V_1 < V_2V1​<V2​.

Now Grammy locates at point SS and she knows the coordinates of all the gliding points p_1, p_2, \dots, p_np1​,p2​,…,pn​. The goal is to reach point TT as fast as possible. Could you tell her the minimum time she has to spend to reach point TT?

Input

The first line contains one integer nn (1\leq n\leq 1\,0001≤n≤1000), denoting the number of gliding points.

The following nn lines describe the gliding points. The ii-th line contains two integers x_i,y_ixi​,yi​ (-1\,000\,000 \leq x_i,y_i \leq 1\,000\,000−1000000≤xi​,yi​≤1000000), representing the coordinates of the ii-th gliding point p_ipi​.

The next line contains four integers S_x,S_y,T_x,T_ySx​,Sy​,Tx​,Ty​ (-1\,000\,000 \leq S_x,S_y,T_x,T_y \leq 1\,000\,000−1000000≤Sx​,Sy​,Tx​,Ty​≤1000000), representing the coordinates of SS and TT.

The next line contains two integers V_1, V_2V1​,V2​ (1\leq V_1 < V_2 \leq 1\,000\,0001≤V1​<V2​≤1000000), representing the speed of walking and gliding.

Output

Output the minimum time Grammy has to spend to reach point TT in one line. Your answer will be considered correct if its absolute or relative error does not exceed 10^{-6}10−6.

Sample 1

Inputcopy	Outputcopy
2 2 1 0 3 0 0 4 0 10 11	0.400000000000

Sample 2

Inputcopy	Outputcopy
2 2 1 -2 0 0 0 4 0 1 2	3.354101966250

Sample 3

Inputcopy	Outputcopy
2 2 1 -2 0 0 0 4 0 1 10000	2.000600000000

 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010;
double g[N][N];
double dist[N];
bool st[N];
int a[N],b[N];
int n;
int x1,yy1,x2,y2;
int v1,v2;
double f(int x1,int y1,int x2,int y2)//计算两点之间的距离
{
    double ans=0;
    ans=sqrt((x1-x2)*(x1-x2)*1.0+(y1-y2)*(y1-y2)*1.0);
    return ans;
}
double dij()
{
    for(int i=1;i<=n;i++)dist[i]=1e18;
    dist[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
        }
        st[t]=1;
        for(int j=1;j<=n;j++)
        {
            if(dist[t]+g[t][j]<dist[j])
                dist[j]=dist[t]+g[t][j];
        }
    }
    return dist[n];
}
signed main()
{
    scanf("%lld",&n);
    n+=2;
    for(int i=2;i<n;i++)scanf("%lld %lld",&a[i],&b[i]);
    scanf("%lld %lld %lld %lld",&x1,&yy1,&x2,&y2);
    scanf("%lld %lld",&v1,&v2);
    g[1][n]=double(f(x1,yy1,x2,y2)*1.0/(v1*1.0));//起点到终点的距离
    for(int i=2;i<n;i++)//起点到每个滑翔点的距离
        g[1][i]=f(x1,yy1,a[i],b[i])/(v1*1.0);
    for(int i=2;i<n;i++)//每个滑翔点到终点的距离
    {
        double k=f(a[i],b[i],x2,y2);
        if(k/(v2*1.0)<=3)
            g[i][n]=double(k/(v2*1.0));
        else
            g[i][n]=3.0+(k-v2*3.0)/(v1*1.0);
    }
    for(int i=2;i<n;i++)//各个滑翔点之间的距离
    {
        for(int j=2;j<n;j++)
        {
            if(i==j)
                continue;
            double k=f(a[i],b[i],a[j],b[j]);
            if(k/(v2*1.0)<=3)
                g[i][j]=k/(v2*1.0);
            else
                g[i][j]=3.0+(k-v2*3.0)/(v1*1.0);
        }
    }
    printf("%.12lf",dij());
}

这题看起来很难，其实就是最短路，先求出起点到终点，起点到每个滑翔点，各个滑翔点之间，每个滑翔点到终点之间的距离，现在就变成一个典型的最短路问题，直接dijkstra算法解决问题。