C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 492K, 提交时间: 2018-10-01 14:26:47

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,a,b,c1,c2;
struct Circle
{
	int x,y,r;
	double d;
};
Circle c[1005];
bool cmp(Circle &c1,Circle &c2)
{
	return c1.d<c2.d;
}
double dist(int x,int y,int c)
{
	return abs((double)a*x+b*y+c)/(sqrt(a*a+b*b));
}
double Cdist(Circle &c1,Circle &c2)
{
	double dd=sqrt((c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y));
	return max(0.0,dd-c1.r-c2.r);
}
double f[1005];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>a>>b>>c1>>c2;
	double ans=abs((double)c1-c2)/(sqrt(a*a+b*b));
	for(int i=1;i<=n;i++)
	{
		cin>>c[i].x>>c[i].y>>c[i].r;
		c[i].d=max(dist(c[i].x,c[i].y,c1)-c[i].r,0.0);
	}
	sort(c+1,c+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		f[i]=c[i].d;
		for(int j=1;j<i;j++) f[i]=min(f[i],f[j]+Cdist(c[i],c[j]));
		ans=min(ans,f[i]+max(dist(c[i].x,c[i].y,c2)-c[i].r,0.0));
	}
	cout<<setiosflags(ios::fixed)<<setprecision(6)<<ans<<endl;
 } 

C++11(clang++ 3.9) 解法, 执行用时: 25ms, 内存消耗: 8160K, 提交时间: 2020-02-27 20:55:14

#include<bits/stdc++.h>
using namespace std;
double g[1005][1005],d[1005];
int n,a,b,c1,c2,x[1005],y[1005],r[1005],i,j,k;
bool v[1005];
int main()
{
	cin>>n>>a>>b>>c1>>c2;
	for(i=1;i<=n;i++) cin>>x[i]>>y[i]>>r[i];
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		g[i][j]=g[j][i]=max(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j],0.0);
		g[0][i]=g[i][0]=max(fabs(a*x[i]+b*y[i]+c1)/sqrt(a*a+b*b)-r[i],0.0);
		g[n+1][i]=g[i][n+1]=max(fabs(a*x[i]+b*y[i]+c2)/sqrt(a*a+b*b)-r[i],0.0);
		
	}
	g[0][n+1]=g[n+1][0]=fabs(c1-c2)/sqrt(a*a+b*b);
	for(i=1;i<=n+1;i++) d[i]=1e15;
	for(i=0;i<=n;i++)
	{
		for(j=0,k=-1;j<=n+1;j++)
		if(!v[j]&&(!~k||d[j]<d[k])) k=j;
		v[k]=1;
		for(j=0;j<=n+1;j++) d[j]=min(d[j],d[k]+g[k][j]);
	}
	printf("%.6lf\n",d[n+1]);
	return 0;
}