WA on #$11$ 求调
查看原帖
WA on #$11$ 求调
1145420
longyitongxue楼主2025/6/23 21:25

Record

虽看了近视后人,但还是不知道怎么调,求各位大佬指点应该在哪里加入什么过 #1111 样例谢谢。

#include<iostream>
#include<math.h>
using namespace std;
int n;
double x[155],y[155],d[155][155],b[155];
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char c;
			cin>>c;
			if(i!=j){
				d[i][j]=((c=='0')?1.0e+50:sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
			}
		}
	}
	floyd();
	double r=0.0,ans=1.0e+50;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(d[i][j]!=1e50){
				b[i]=max(b[i],d[i][j]);
				r=max(r,b[i]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j&&d[i][j]==1.0e+50){
				double tmp=b[i]+b[j]+sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
				ans=min(ans,tmp);
			}
		}
	}
	printf("%.6lf",max(r,ans));
	return 0;
}
2025/6/23 21:25
加载中...