题解 | #New Game!#

/*
建立两个虚拟远点 0 和 n+1 ，分别为 c1 和 c2 的虚拟远点
但是
不用看了 数据太水了
*/

#include <bits/stdc++.h>

using namespace std;

typedef double ld;

const int N = 1010;

int n;
ld A,B,c1,c2;
ld g[N][N],d[N];
bool str[N];

ld path(ld A,ld B,ld c,ld x,ld y) //点到直线的距离
{
	return abs(A*x+B*y+c)/sqrt(A*A+B*B);
}

struct Node
{
	ld x,y,r;
}a[N];

void dijkstra()
{
	//memset(d,1e9,sizeof N*2);
    for(int i=0;i<=n+1;i++) d[i]=1e9;
	d[0]=0;
	
	for(int i=0;i<=n+1;i++)
	{
		int t=-1;
		for(int j=0;j<=n+1;j++)
		{
			if(!str[j]&&(t==-1||d[t]>d[j]))
			{
				t=j;
			}
		}
		
		for(int j=0;j<=n+1;j++)
		{
			d[j]=min(d[j],d[t]+g[t][j]);
		}
		str[t]=true;
	}
	
	cout<<d[n+1]<<'\n';
}

int main()
{
	cin>>n>>A>>B>>c1>>c2;
	g[0][n+1]=g[n+1][0]=1e9;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].r;
		ld x1=a[i].x,y1=a[i].y,r1=a[i].r;
		g[0][i]=g[i][0]=max(0.0,path(A,B,c1,x1,y1)-r1);
		g[n+1][i]=g[i][n+1]=max(0.0,path(A,B,c2,x1,y1)-r1);
	}
	
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			g[i][j]=g[j][i]=max(0.0,sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))-a[i].r-a[j].r);
		}
		
	dijkstra();
	
	return 0;
}