链接：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 个圆 。角色在直线上、圆上、园内行走不消耗体力。在其他位置上由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 即算正确。

输入

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

输出

0.236068

解题思路

首先算出两条直线和n个圆相互之间的距离：圆与圆：圆心距离减去两个半径的距离；圆与线：圆心到直线的距离减去半径；线与线：就是两条平行线的距离，若之间的距离小于0，应定为0(距离不为负)。最后跑一边最短路就行了。

#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
double inf = 99999999;
int t, vis[1010];
double map[1010][1010], dis[1010];
struct node {
	int x, y, r;
}lep[1010];
void Dijkstra(int s)
{
	int i, j, k, data;
	double min;
	for (i = 0; i < t; i++)
	{
		dis[i] = inf;
		vis[i] = 0;
	}
	dis[s] = 0;
	for (i = 0; i < t; i++)
	{
		min = inf;
		for (j = 0; j < t; j++)
		{
			if (!vis[j] && dis[j] < min)
			{
				min = dis[j];
				data = j;
			}
		}
		vis[data] = 1;
		for (k = 0; k < t; k++)
		{
			if (map[data][k] < inf)
			{
				if (!vis[k] && dis[k] > dis[data] + map[data][k])
					dis[k] = dis[data] + map[data][k];
			}
		}
	}
}
int main()
{
	int n, A, B, C1, C2;
	while (cin >> n >> A >> B >> C1 >> C2)
	{
		for (int i = 1; i <= n; i++)
		{
			cin >> lep[i].x >> lep[i].y >> lep[i].r;
			for (int j = 1; j < i; j++)
			{
				map[i][j] = map[j][i] = sqrt((lep[i].x - lep[j].x) * (lep[i].x - lep[j].x) + (lep[i].y - lep[j].y) * (lep[i].y - lep[j].y)) - lep[i].r - lep[j].r;
					if (map[i][j] < 0)
						map[i][j] = map[j][i] = 0;
			}
		}
		for (int i = 1; i <= n; i++)
		{
			map[0][i] = map[i][0] = fabs(A * lep[i].x + B * lep[i].y + C1) / sqrt(A * A + B * B) - lep[i].r;
			if (map[0][i] < 0)
				map[0][i] = map[i][0] = 0;
		}
		for (int i = 1; i <= n; i++)
		{
			map[n + 1][i] = map[i][n + 1] = fabs(A * lep[i].x + B * lep[i].y + C2) / sqrt(A * A + B * B) - lep[i].r;
			if (map[n + 1][i] < 0)
				map[n + 1][i] = map[i][n + 1] = 0;
		}
		map[0][n + 1] = map[n + 1][0] = fabs(C1 - C2) / sqrt(A * A + B * B);
		t = n + 2;
		Dijkstra(0);
		cout << dis[n + 1] << endl;
	}
	return 0;
}