Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
1.9 kB
0
Indexable
Never
#include <iostream>
using namespace std;

#define MAX 9999999
using namespace std;

int n;
int mem;
bool visited[201];
int parent[201];
int key[201];
int arr[201][201];

int x[201], y[201], k[201];

void Dijkstra(int u){
	key[u] = 0;
	for(int i=0; i<n; i++){
		/*for(int p=0; p<n; p++){
			if(visited[p] == false){
				mem = p;
				break;
			}
		}*/
		//int min = key[mem];
		int min = MAX;
		mem = -1;
		for(int j=0; j<n; j++){
			if(visited[j] == false){
				if(key[j] < min){
					min = key[j];
					mem = j;
				}
			}
		}

		if(mem == -1)
			return;

		visited[mem] = true;
		for(int k=0; k<n; k++){
			if(visited[k] == false && arr[mem][k] != 0){
				if(key[k] > key[mem] + arr[mem][k]){
					key[k] = key[mem] + arr[mem][k];
				}
			}
		}
	}
}

int main(){
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	
	for(int tc=1; tc<=t; tc++){
		cin >> n;
		for(int i=0; i<n; i++){
			key[i] = MAX;
			parent[i] = -1;
			visited[i] = false;
		}

		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				arr[i][j] = 0;
			}
		}

		for(int i=0; i<n; i++){
			cin >> x[i] >> y[i] >> k[i];
		}

		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				long long td = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
				long long kc1 = (40 + k[i] + k[j]);

				long long kc2 = (90 + k[i] + k[j]);

				if(i==j){
					arr[i][j] = 0;
				}
				else if(td <= kc1 * kc1){
					arr[i][j] = 1;
				}
				else if(td <= kc2 * kc2){
					arr[i][j] = 400;
				} 
				else{
					arr[i][j] = 0;
				}
			}
		}

		/*cout << endl;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				cout << arr[i][j] << " ";
			}
			cout << endl;
		}*/

		Dijkstra(0);

		if(key[n-1] == MAX){
			cout << "-1" << endl;
		}
		else
			cout << key[n-1]/400 << " " << key[n-1]%400 << endl;

		
	}
	return 0;
}