#11WA求助
查看原帖
#11WA求助
781761
shaotianyu楼主2024/8/25 15:24

RtRt 被hack了求助

Code:Code:

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std;

const int N=150+11;
struct node{
	int x,y;
}q[N*5];

int n;
double w[N][N],dis[N];
char in[N][N];

double distance(int a,int b){
	return 1.0*sqrt(1.0*(q[a].x-q[b].x)*(q[a].x-q[b].x)+1.0*(q[a].y-q[b].y)*(q[a].y-q[b].y));
}

int main(){
	cin>>n;
	memset(w,127,sizeof(w));
	memset(dis,0,sizeof(dis));
	for(int i=1;i<=n;i++) cin>>q[i].x>>q[i].y;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>in[i][j];
			if(in[i][j]=='1') w[j][i]=w[i][j]=distance(i,j);
		}
	}
	
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i!=j&&j!=k&&k!=i&&w[i][k]+w[k][j]<w[i][j]) w[i][j]=w[i][k]+w[k][j];
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(w[i][j]<w[0][0]&&i!=j&&w[i][j]>dis[i]) dis[i]=w[i][j];
		}
	}
	
	double minn=w[0][0];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(w[i][j]==w[0][0]&&i!=j&&distance(i,j)+dis[i]+dis[j]<minn) {
				minn=distance(i,j)+dis[i]+dis[j];
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		if(dis[i]>minn) minn=dis[i];
	}
	printf("%.6lf",minn);
	
	return 0;
}

2024/8/25 15:24
加载中...