# 牛客国庆集训派对Day1L New Game!（最短路）

## New Game!

### 题目描述

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

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

### 输入

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

### 输出

0.236068

### 链接

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

### 代码

• 答案正确 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)
else
}
for (int i = 1; i <= n; ++i) // 圆与终点
{
double w = dist2(C2, circle[i]);
if (w > eps)
else
}
for (int i = 1; i <= n; ++i) // 圆间
{
for (int j = 1; j <= n; ++j)
{
double w = dist1(circle[i], circle[j]);
if (w > eps)
{
}
else
{
}