MENU

牛客国庆集训派对Day1L New Game!(最短路)

2018 年 10 月 24 日 • 阅读: 1027 • 图论阅读设置

New Game!

题目描述

Eagle Jump公司正在开发一款新的游戏。Hifumi Takimoto作为其中的员工,获得了提前试玩的机会。现在她正在试图通过一个迷宫。
这个迷宫有一些特点。为了方便描述,我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线$ L_1:Ax+By+C1=0, L_2:Ax+By+C2=0$,还有 n 个圆 $C_i:(x-x_i)^2 + (y - y_i)^2 = r_i^2$。角色在直线上、圆上、圆内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。
Hifumi Takimoto想从 $L_1$ 出发,走到 $L_2$ 。请计算最少需要多少体力。

输入描述

第一行五个正整数 $n,A,B,C_1,C_2$ ($1≤ n ≤ 1000, -10000 ≤ A,B,C_1,C_2 ≤ 10000$),其中 A,B 不同时为 0。
接下来 n 行每行三个整数 $x,y,r(-10000 ≤ x,y ≤ 10000, 1≤ r ≤ 10000) $表示一个圆心为 $(x,y)$,半径为 $r$的圆。

输出描述

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

输入

2 0 1 0 -4
0 1 1
1 3 1

输出

0.236068

链接

https://www.nowcoder.com/acm/contest/201/L

题意

如题,问从直线$L_1$到$L_2$的最短距离。

题解

题目关键在角色在直线上、圆上、圆内行走不消耗体力,所以可以把直线和圆都看成一个点,然后建图,直线$L_1$为起点,直线 $L_2$为终点,跑最短路径即可。

代码

  • 答案正确 76ms 32608KB 2604
#include <bits/stdc++.h>
using namespace std;
const double inf = 1e9;
const double eps = 1e-9;
const int maxn = 1010;
int N, n;
double A, B, C1, C2;
double dist[maxn];
bool vis[maxn];

struct Node
{
    int v;
    double c;
    Node (int _v, double _c): v(_v), c(_c) {}
    bool operator < (const Node & r) const
    {
        return c > r.c;
    }
};

struct Edge
{
    int to;
    double cost;
    Edge(int _to, double _cost): to(_to), cost(_cost) {}
};

vector <Edge> edge[maxn];

void addedge(int u, int v, double w)
{
    edge[u].push_back(Edge(v, w));
}

struct Circle
{
    double x, y, r;
}circle[maxn];

double dist1(Circle a, Circle b) // 两个“圆”的距离
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) - a.r - b.r;
}

double dist2(double C, Circle d) // “圆”到直线的距离
{
    return (fabs(A * d.x + B * d.y  + C) / sqrt(A * A + B * B) - d.r);
}

double dijkstra(int s, int t) // 最短路
{
    for (int i = 0; i <= N; ++i)
    {
        dist[i] = inf;
        vis[i] = false;
    }
    dist[s] = 0;
    priority_queue <Node> Q;
    Q.push(Node(s, dist[s]));
    while (!Q.empty())
    {
        Node tmp = Q.top();
        Q.pop();
        int u = tmp.v;
        if (u == t) //  到达t即返回
            return tmp.c;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < edge[u].size(); ++i)
        {
            int v = edge[u][i].to;
            double cost = edge[u][i].cost;
            if (!vis[v] && dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                Q.push(Node(v, dist[v]));
            }
        }
    }
    return 0;
}

int main()
{
    scanf("%d%lf%lf%lf%lf", &n, &A, &B, &C1, &C2);
    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf%lf", &circle[i].x, &circle[i].y, &circle[i].r);
    N = n + 1; // 总点数
    for (int i = 1; i <= n; ++i) // 起点与圆
    {
        double w = dist2(C1, circle[i]);
        if (w > eps)
            addedge(0, i, w);
        else
            addedge(0, i, 0);
    }
    for (int i = 1; i <= n; ++i) // 圆与终点
    {
        double w = dist2(C2, circle[i]);
        if (w > eps)
            addedge(i, N, w);
        else
            addedge(i, N, 0);
    }
    for (int i = 1; i <= n; ++i) // 圆间
    {
        for (int j = 1; j <= n; ++j)
        {
            double w = dist1(circle[i], circle[j]);
            if (w > eps)
            {
                addedge(i, j, w);
                addedge(j, i, w);
            }
            else
            {
                addedge(i, j, 0);
                addedge(j, i, 0);
            }
        }
    }
    double ans = dijkstra(0, N);
    printf("%.7f\n", ans);
    return 0;
}

The end.
2018-10-24 星期三
最后编辑于: 2018 年 11 月 16 日