WA10求调*2
查看原帖
WA10求调*2
362101
_TLEer_的小号楼主2021/4/24 10:05

RT.

#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
double checkaround(int Rd,int S,int Rx){
	return abs(S*Rd*1.0/Rx);
}
double OJLD(int x1,int y1,int x2,int y2){
    return sqrt(pow((x1-x2)*1.0,2)+pow((y1-y2)*1.0,2));
}
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]))return true;
	return false;
}
bool check[2000];
double speed[2000],answ,lastansw;
int n,x_t,y_t,qi,z,a[100010];
queue<int> q;
void BFS(){
	speed[qi]=10000.0;
	check[qi]=true;
	q.push(qi);
	while(!q.empty()){
		int p=q.front();q.pop();
		for(int i=1;i<=n;i++){
			if(checka(p,i)&&!check[i]){
				check[i]=true;
				speed[i]=checkaround(R[p],speed[p],R[i]);
				a[i]=p;
				if(i==z)return;
				q.push(i);
			}
		}
	}
}
int main(){
	memset(check,0,sizeof(check));
	cin>>n>>x_t>>y_t;
	for(int i=1;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();
	for(int i=z;i;i=a[i])
		answ+=speed[i];
	cout<<(int)(answ+0.000001)<<endl;
	return 0;
}
2021/4/24 10:05
加载中...