Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.6 kB
3
Indexable
Never
#include<iostream>
using namespace std;

#define MAXSIZE 201

int xy[MAXSIZE][2];
int R[MAXSIZE];
int dis[MAXSIZE][MAXSIZE];
int visited[MAXSIZE];
int parent[MAXSIZE];
int D[MAXSIZE];
int nTestcase, N, current, currentTemp, sumVisit, Far, Near;

long long pow_xy(int x1, int x2, int y1, int y2){
	return (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1);
}


int main(){
	freopen("input.txt","r",stdin);
	cin >> nTestcase;
	for(int testcase = 1; testcase <= nTestcase; testcase++){
		cin >> N;
		for(int i = 0; i < N; i++){
			parent[i] = -1;
		}
		for(int i = 0; i < N; i++){
			cin >> xy[i][0] >> xy[i][1] >> R[i];
		}
		for(int i = 0; i < N; i++){
			for(int j = i; j < N; j++){
				int temp = pow_xy(xy[i][0],xy[j][0],xy[i][1],xy[j][1]);
				if(temp > (R[i] + R[j] + 90)*(R[i] + R[j] + 90)){
					dis[i][j] = 10000000000;
				}else if(temp > (R[i] + R[j] + 40)*(R[i] + R[j] + 40)){
					dis[i][j] = 300;
				}else{
					dis[i][j] = 1;
				}
			}
		}
		
		for(int i = 0; i < N; i++){
			D[i] = 10000000000;
			visited[i] = 0;
		}
		D[0] = 0;

		for(int i = 0; i < N; i++){
			int min = 10000000000;
			currentTemp = -1;
			for(int j = 0; j < N; j++){
				if((min > D[j] || currentTemp == -1) && visited[j] == 0){
					currentTemp = j;
					min = D[j];
				}
			}
			visited[currentTemp] = 1;
			for(int j = 0; j < N; j++){
				D[j] = D[j] > D[currentTemp] + dis[currentTemp][j] ? D[currentTemp] + dis[currentTemp][j] : D[j];
			}
		}

		if(D[N - 1] == 10000000000){
			cout << -1 << endl;
		}else{
			cout << D[N - 1] / 300 << " " << D[N - 1] % 300 << endl;
		}
	}
	return 0;
}