链接：https://ac.nowcoder.com/acm/contest/201/L
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
Special Judge, 64bit IO Format: %lld
空间限制：C/C++ 1048576K，其他语言2097152K
Special Judge, 64bit IO Format: %lld
题目描
Eagle Jump公司正在开发一款新的游戏。Hifumi Takimoto作为其中的员工，获得了提前试玩的机会。现在她正在试图通过一个迷宫。
这个迷宫有一些特点。为了方便描述，我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线 L:Ax+By+C=0, L:Ax+By+C=0，还有 n 个圆 Ci:(x−xi)2+(y−yi)2=ri2Ci:(x−xi)2+(y−yi)2=ri2。角色在直线上、圆上、园内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。
Hifumi Takimoto想从 L 出发，走到 L 。请计算最少需要多少体力。
输入描述:
第一行五个正整数 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
即算正确。
示例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 ;
}