牛客国庆集训派对Day1 L-New Game!（最短路）

时间：2023-12-22 09:14:56

链接：https://www.nowcoder.com/acm/contest/201/L

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 1048576K，其他语言2097152K

Special Judge, 64bit IO Format: %lld

题目描述

Eagle Jump公司正在开发一款新的游戏。Hifumi Takimoto作为其中的员工，获得了提前试玩的机会。现在她正在试图通过一个迷宫。

这个迷宫有一些特点。为了方便描述，我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线 L1:Ax+By+C1=0, L2:Ax+By+C2=0，还有 n 个圆 牛客国庆集训派对Day1 L-New Game!（最短路）。角色在直线上、圆上、园内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。

Hifumi Takimoto想从 L1 出发，走到 L2 。请计算最少需要多少体力。

输入描述:

第一行五个正整数 n,A,B,C1,C2 (1≤ n ≤ 1000, -10000 ≤ A,B,C1,C2 ≤ 10000)，其中 A,B 不同时为 0。

接下来 n 行每行三个整数 x,y,r(-10000 ≤ x,y ≤ 10000, 1≤ r ≤ 10000) 表示一个圆心为 (x,y)，半径为 r 的圆。

输出描述:

仅一行一个实数表示答案。与正确结果的绝对误差或者相对误差不超过 10-4 即算正确。

示例1

输入

2 0 1 0 -4

0 1 1

1 3 1

输出

0.236068

思路

将第一条线作为起点（第0个点），第二条线作为终点（第n+1个点），第i个圆作为第i个点，这些线与线，线与圆的最短距离作为两点间的权值进行建图，然后求最短路就可以了

AC代码

//数据好水，这个代码有好多样例都过不去，但是竟然AC了，我以前用的迪杰斯特拉模板不知道为什么会WA，换成百度找的AC代码里的模板过了。。。好多bug，懒得改了，思路大致就是这样

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#define ll long long

#define ull unsigned long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x7f7f7f7f

#define lson o<<1

#define rson o<<1|1

const double E=exp(1);

const int maxn=1e3+10;

const int mod=1e9+7;

using namespace std;

struct wzy

{

    int x,y,r;

}p[maxn];

inline double juli(int a,int b,int c,int x,int y)

{

    double _=sqrt(a*1.0*a*1.0+b*1.0*b*1.0);

    double __=a*1.0*x+b*1.0*y+c*1.0;

    return fabs(__/_);

}

inline double juli1(int x,int y,int x1,int y1)

{

    double _=sqrt(fabs(x*1.0-x1*1.0)*fabs(x*1.0-x1*1.0)+fabs(y*1.0-y1*1.0)*fabs(y*1.0-y1*1.0));

    return _;

}

double edge[maxn][maxn];

int flag[maxn];     //flag[i]标记节点i是否被查询

double dis[maxn];   //dis[i]表示节点i距离起始节点的最短距离

int n,m,a,b,c1,c2;  //n个点，m条边

inline void Dijkstra()

{

    memset(flag,0,sizeof(flag));

    for(int i=0;i<=n+1;i++)

        dis[i]=INF;

    dis[0]=0;

    while(1)

    {

        int v=-1;

        for(int i=0;i<=n+1;i++)

        {

            if(!flag[i] && (v==-1 || dis[i]<dis[v]))

                v=i;

        }

        if(v==-1)break;

        flag[v]=1;

        for(int i=0;i<=n+1;i++)

            dis[i]=min(dis[i],dis[v]+edge[v][i]);

    }

}

int main(int argc, char const *argv[])

{

    scanf("%d%d%d%d%d",&n,&a,&b,&c1,&c2);

    for(int i=0;i<maxn;i++)

        for(int j=0;j<maxn;j++)

            edge[i][j]=edge[j][i]=INF;

    for(int i=1;i<=n;i++)

        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].r);

    // 求第一个直线

    for(int i=1;i<=n;i++)

    {

        double res=juli(a,b,c1,p[i].x,p[i].y)-p[i].r*1.0;

        if(res<0)

            edge[0][i]=edge[i][0]=0.0;

        else

            edge[0][i]=edge[i][0]=res;

    }

    // 求第二个直线

    for(int i=1;i<=n;i++)

    {

        double res=juli(a,b,c2,p[i].x,p[i].y)-p[i].r*1.0;

        if(res<0)

            edge[n+1][i]=edge[i][n+1]=0.0;

        else

            edge[n+1][i]=edge[i][n+1]=res;

    }

    // 两圆距离

    for(int i=1;i<=n;i++)

    {

        for(int j=i+1;j<=n;j++)

        {

            double res=juli1(p[i].x,p[i].y,p[j].x,p[j].y)-p[i].r*1.0-p[j].r*1.0;

            if(res<0)

                edge[j][i]=edge[i][j]=0.0;

            else

                edge[j][i]=edge[i][j]=res;

        }

    }

    Dijkstra();

    printf("%.6lf\n",dis[n+1]);

    return 0;

}

相关文章