题解 | #New Game!#

实际上就是把直线和圆都弱化成一个点 第一个圆就是第一个点 第n个圆就是第n个点 令起点为0（l1） 令终点为n+1（l2） 然后建图 就把题目弱化为dijkstra的模板题目了 注意memset这里使用会有错误 具体原因等查明来补

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n;
double g[N][N];
bool st[N];
double dis[N];

struct node{
	double x, y, r;
}cir[N];

double pl(double a,double b,double c,double x,double y)
{
	return abs(a*x+b*y+c)/sqrt(a*a+b*b);
}//点到直线

double pp(int x1,int x2,int y1,int y2)
{
	return sqrt(pow(x2-x1,2)+pow(y2-y1,2));
}//点到点

void dij()//模板
{
	//memset(d,0x3f,sizeof d);此法不可取
	for(int i=0;i<=n+1;i++) dis[i]=1e9;
	dis[0]=0;
	for(int i=0;i<=n+1;i++)
	{
		int t=-1;
		for(int j=0;j<=n+1;j++)
		{
			if(!st[j]&&(t==-1||dis[t]>dis[j]))
				t=j;
		}
		st[t]=1;
		for(int i=0;i<=n+1;i++)
		{
			dis[i]=min(dis[i],dis[t]+g[t][i]);
		}
	}
	cout<<dis[n+1]<<endl;
}


int main()
{
	cin>>n;
	double a,b,c1,c2;cin>>a>>b>>c1>>c2;
	//memset(g,0x3,sizeof g);此法不可取
	g[0][n+1]=g[n+1][0]=1e9;
	for(int i=1;i<=n;i++)
	{
		cin>>cir[i].x>>cir[i].y>>cir[i].r;
		double x=cir[i].x,y=cir[i].y,r=cir[i].r;
		//分别计算起点与终点 和 各个圆点之间的距离
		g[0][i]=g[i][0]=max(0.0,pl(a,b,c1,x,y)-r);//点 圆叠在一起弱化为g[i][j]=0
		g[n+1][i]=g[i][n+1]=max(0.0,pl(a,b,c2,x,y)-r);
	}
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
	{
		//计算各个圆点之间的距离
		//俩圆叠在一起弱化为g[i][j]=0
		g[i][j]=g[j][i]=max(0.0,pp(cir[i].x,cir[j].x,cir[i].y,cir[j].y)-cir[i].r-cir[j].r);
	}
	dij();
	return 0;
}