牛客国庆集训派对Day1 L New Game!（堆优化dijkstra+建图）

时间：2021-06-10 14:55:30

链接：https://ac.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 个圆 Ci:(x−xi)2+(y−yi)2=ri2Ci:(x−xi)2+(y−yi)2=ri2。角色在直线上、圆上、园内行走不消耗体力。在其他位置上由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

题目大意：

给你两条平行的直线，n个圆，在直线和圆上运动不需要能量（距离），问从一条直线到另一条直线最少需要多少距离。

从一条直线到另一条直线，一共可能经过三种路径。

直线到直线，直线到圆，圆到圆，都是无向边。

这三种分别有1，2n，n^2条边，注意链式前向星开空间需要乘2。

以后最好还是用dijkstra的堆优化版本吧，spfa被卡了。

总结一下各种最短路算法的适用条件（V为点数，E为边数）：

Floyd：V^3

Spfa：平均kE(一般k为小常数2，表示每个点平均进队次数) 最差VE 可见稠密图卡爆，故若正权图就用dijkstra吧，只有负权图用spfa

Dijkstra：普通V^2 堆优化ElogV 可见稠密图上普通版，其他只要都上堆优化版，不过只适用于正权图的情况

还涉及到一点计算几何。要入门计算几何了嘛？233

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <string>

#include <cmath>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

typedef long long ll;

const double eps=1e-;

const int mod=;

const double inf=;

const int maxn=;

const int maxm=;

using namespace std;

struct tcircle

{

    double x,y,r;

};

tcircle cir[maxn+];

double dotdot(double x1,double y1,double x2,double y2)

{

    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

double dotline(double x,double y,double a,double b,double c)

{

    return fabs(a*x+b*y+c)/sqrt(a*a+b*b);

}

double lineline(double a,double b,double c1,double c2)

{

    return fabs(c1-c2)/sqrt(a*a+b*b);

}

int to[(maxn+)*(maxn+)+];

double w[(maxn+)*(maxn+)+];

int nex[(maxn+)*(maxn+)+];

int head[maxn+],cnt=;

void addedge(int u,int v,double wei)

{

    to[cnt]=v;w[cnt]=wei;

    nex[cnt]=head[u];head[u]=cnt++;

    to[cnt]=u;w[cnt]=wei;

    nex[cnt]=head[v];head[v]=cnt++;

}

struct tnode

{

    double d;

    int u;

    bool operator<(const tnode& rhs) const

    {

        return d>rhs.d;

    }

};

double dis[maxn+];

int done[maxn+];

int main()

{

    int n;

    double a,b,c1,c2;

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

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

        scanf("%lf%lf%lf",&cir[i].x,&cir[i].y,&cir[i].r);

    memset(head,-,sizeof(head));

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

    {

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

        {

            double d=dotdot(cir[i].x,cir[i].y,cir[j].x,cir[j].y);

            if(d>cir[i].r+cir[j].r)

                addedge(i,j,d-cir[i].r-cir[j].r);

            else

                addedge(i,j,);

        }

    }

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

    {

        double d;

        d=dotline(cir[i].x,cir[i].y,a,b,c1);

        if(d>cir[i].r)

            addedge(i,n+,d-cir[i].r);

        else

            addedge(i,n+,);

        d=dotline(cir[i].x,cir[i].y,a,b,c2);

        if(d>cir[i].r)

            addedge(i,n+,d-cir[i].r);

        else

            addedge(i,n+,);

    }

    addedge(n+,n+,lineline(a,b,c1,c2));

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

        dis[i]=inf;

    dis[n+]=;

    memset(done,,sizeof(done));

    priority_queue<tnode> q;

    q.push((tnode){,n+});

    while(!q.empty())

    {

        tnode x=q.top();q.pop();

        int u=x.u;

        if(done[u])

            continue;

        done[u]=;

        for(int i=head[u];i!=-;i=nex[i])

        {

            int l=to[i];

            if(dis[l]>dis[u]+w[i])

            {

                dis[l]=dis[u]+w[i];

                q.push((tnode){dis[l],l});

            }

        }

    }

    printf("%f\n",dis[n+]);

    return ;

}

相关文章