41AC WA了8个,求调
查看原帖
41AC WA了8个,求调
1001043
iranai楼主2023/10/31 20:55
#include<bits/stdc++.h>
using namespace std;
double xs,ys,xt,yt;
int n;
int h[10010];
int to[10000010];
int nt[10000010];
double w[10000010];
int idx;
bool v[10010];
double d[10010];
void add(int x,int y,double z){
	to[idx]=y;
	w[idx]=z;
	nt[idx]=h[x];
	h[x]=idx;
	idx++;
}
typedef pair<double,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > hp;
void dijkstra_hp(int u){
	d[u]=0;
	hp.push((PII){0,u});
	while(hp.size()>0){
		PII top=hp.top();
		hp.pop();
		int t=top.second;
		if(!v[t]){
			v[t]=true;
			for(int i=h[t];i!=-1;i=nt[i]){
				int j=to[i];
				if(d[t]+w[i]<d[j]) d[j]=d[t]+w[i],hp.push((PII){d[j],j});
			}
		}
	}
}
struct E{
	double x;
	double y;
	double r;
} a[10010];
int p;
int main(){
	memset(h,-1,sizeof(h));
	scanf("%lf%lf%lf%lf",&xs,&ys,&xt,&yt);
	a[1]=(E){0,0,0};
	xt-=xs;
	yt-=ys;
	scanf("%d",&n);
	for(int i=1;i<=n+2;i++) d[i]=1000000000;
	for(int i=2;i<=n+1;i++){
		double x,y,r;
		scanf("%lf%lf%lf",&x,&y,&r);
		x-=xs;
		y-=ys;
		if(abs(x-xt)<=0.000000001&&abs(y-yt)<=0.000000001) p=i;
		a[i]=(E){x,y,r};
	}
	if(p==0){
		p=n+2;
		a[n+2]=(E){xt,yt,0};
	}
	for(int i=1;i<=max(p-1,n);i++){
		for(int j=i+1;j<=max(p,n+1);j++){
			double ww=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;
			if(ww<0) ww=0;
			add(i,j,ww);
			add(j,i,ww);
		}
	}
	dijkstra_hp(1);
	printf("%.10f\n",d[p]);
	return 0;
}
2023/10/31 20:55
加载中...