Untitled

mail@pastecode.io avatar
unknown
plain_text
21 days ago
1.6 kB
0
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

#define MAX 1000000000

int Map[201][201];
int visited[201], dist[201], R[201];
int xy[201][2];
int nTestcase, N, Min, min_index;

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++) {
			visited[i] = 0;
			dist[i] = MAX;
		}
		dist[0] = 0;
		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 = 0; j < N; j++) {
				int value = (xy[j][0] - xy[i][0]) * (xy[j][0] - xy[i][0]) + (xy[j][1] - xy[i][1]) * (xy[j][1] - xy[i][1]);
				if (value > (90 + R[i] + R[j]) * (90 + R[i] + R[j])) {
					Map[i][j] = MAX;
				}else if (value > (40 + R[i] + R[j]) * (40 + R[i] + R[j])) {
					Map[i][j] = 200;
				}
				else if (value == 0) {
					Map[i][j] = 0;
				}else
				{
					Map[i][j] = 1;
				}
			}
		}
		for (int i = 0; i < N - 1; i++) {
			Min = MAX;
			for (int j = 0; j < N; j++) {
				if (!visited[j] && dist[j] <= Min) {
					Min = dist[j];
					min_index = j;
				}
			}
			visited[min_index] = 1;
			for (int v = 0; v < N; v++) {
				if (!visited[v] && dist[min_index] != MAX && dist[v] > dist[min_index] + Map[min_index][v]) {
					dist[v] = dist[min_index] + Map[min_index][v];
				}
			}
		}

		if (dist[N - 1] == MAX) {
			cout << -1 << endl;
		}
		else {
			cout << dist[N - 1] / 200 << " " << dist[N - 1] % 200 << endl;
		}
	}
	return 0;
}