WA10求调
查看原帖
WA10求调
362101
_TLEer_的小号楼主2020/10/31 10:48

RT.

#include<iostream>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
double checkaround(int Rd,double S,int Rx){
	return abs(S*Rd/Rx);
}
int OJLD(int x1,int y1,int x2,int y2){
	return abs(x1-x2)*abs(x1-x2)+abs(y1-y2)*abs(y1-y2);
}
int X[2000],Y[2000],R[2000];
bool checka(int n,int m){
	if(OJLD(X[n],Y[n],X[m],Y[m])==(R[n]+R[m])*(R[n]+R[m]))return true;
	return false;
}
bool check[2000];
double speed[2000],answ;
int n,x_t,y_t,qi,z;
queue<int> q;
void BFS(){
	answ=speed[qi]=10000.0;
	check[qi]=true;
	q.push(qi);
	while(!q.empty()){
		int tst=q.front();
		q.pop();
		for(int i=0;i<n;i++){
			if(checka(tst,i)&&!check[i]){
				check[i]=true;
				speed[i]=checkaround(R[tst],speed[tst],R[i]);
				answ+=speed[i];
				if(i==z)return;
				q.push(i);
			}
		}
	}
}
int main(){
	cin>>n>>x_t>>y_t;
	for(int i=0;i<n;i++){
		cin>>X[i]>>Y[i]>>R[i];
		if(!X[i]&&!Y[i])qi=i;
		if(X[i]==x_t&&Y[i]==y_t)z=i;
	}
	BFS();
	cout<<(int)answ<<endl;
	return 0;
}
2020/10/31 10:48
加载中...