Untitled

mail@pastecode.io avatar
unknown
plain_text
11 days ago
1.9 kB
0
Indexable
Never
#include <iostream>
using namespace std;

int T, tc;
int N;
int XYR[205][3];
int map[205][205];
int dist[205];
int visit[205];

#define INF 10000000
#define MINF(a,b) a<=b?a:b
#define STEP(d) d<=40?1:1000

void init_dist(){
	for(int i=0; i<N; i++){
		dist[i] = INF;
	}
}

void clr_visit(){
	for(int i=0; i<N; i++){
		visit[i]=0;
	}
}

int isVisitAll(){
	for(int i=0; i<N; i++){
		if(visit[i]==0)
			return 0;
	}
	return 1;
}

int sqrt(int input){
	int ans=0;
	for(int i=0; i<=input; i++){
		if(i*i>input){
			ans=i-1;
			break;
		}
	}
	if((input-ans*ans)!=0){
		ans++;
	}
	return ans;
}

int main()
{
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> T;
	for(tc=1; tc<=T; tc++)
	{
		cin >> N;
		for(int i=0; i<N; i++){
			cin >> XYR[i][0] >> XYR[i][1] >> XYR[i][2];
		}
		for(int i=0; i<N; i++)
		{
			for(int j=i; j<N; j++)
			{
				if(i==j)
					map[i][j]=map[j][i]=0;
				else{
					int a = XYR[i][0] - XYR[j][0];
					int b = XYR[i][1] - XYR[j][1];
					int d = sqrt(a*a+b*b)-XYR[i][2]-XYR[j][2];
					if (d <= 40) {
						map[i][j] = map[j][i] = 1;
					} else if (d > 40 && d <= 90) {
						map[i][j] = map[j][i] = 1000;
					} else {
						map[i][j] = map[j][i] = -1;
					}
				}
			}
		}
		//Solve
		init_dist();
		clr_visit();
		dist[0]=0;
		while(isVisitAll()==0)
		{
			int min = INF+1;
			int cur=0;
			for(int i=0; i<N; i++){
				if(dist[i]<min && visit[i]==0){
					min = dist[i];
					cur = i;
				}
			}
			visit[cur]=1;
			for(int i=0; i<N; i++){
				if (map[cur][i] == -1) continue;
				if(i!=cur){
					dist[i] = MINF(dist[i], dist[cur]+map[cur][i]);
				}
			}
		}
		if(dist[N-1]!=INF){
			int long_jmp = dist[N-1] / 1000;
			int short_jmp = dist[N-1] % 1000;
			cout << long_jmp << " " << short_jmp << endl;
		} else {
			cout << -1 << endl;
		}
		//cout << endl;
	}
	return 0;
}
Leave a Comment