the_frog

 avatar
duyvan
plain_text
a year ago
1.9 kB
9
Indexable
#include <iostream>

using namespace std;

int T, N;
int Oxy[200][3];
int results, jump_short, jump_long, tt_short;
int matrix[200][200];
int visit[200];

struct Node
{
	int r, c;
};

int Queue[1000000];
int front, rear;
void enQueue(int x){
	rear++;
	Queue[rear] = x;
}

int deQueue(){
	front++;
	return Queue[front];
}

int distan(int index1, int index2){
	int a = Oxy[index1][0] - Oxy[index2][0];
	int b = Oxy[index1][1] - Oxy[index2][1];
	return (a*a + b*b);
}

int check(int index1, int index2){
	int dis = distan(index1,index2);
	int a = 40 + Oxy[index1][2] + Oxy[index2][2];
	int b = 90 + Oxy[index1][2] + Oxy[index2][2];
	if (a*a > dis) return 1;
	else if (b*b > dis) return 10000;
	return 0;
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> T;
	for (int t = 0; t < T; t++){
		cin >> N;
		results = -1;
		jump_short = jump_long = 100000;
		for (int i = 0; i < N; i++){
			cin >> Oxy[i][0] >> Oxy[i][1] >> Oxy[i][2];
			visit[i] = -1;
		}
		for (int i = 0; i < N; i++){
			for (int j = i + 1; j < N; j++){
				matrix[i][j] = check(i,j);
				matrix[j][i] = matrix[i][j];
			}
			matrix[i][i] = -1;
		}
		front = rear = -1;
		enQueue(0);
		visit[0] = 0;
		while (front != rear){
			int node = deQueue();
			if (node == N - 1) {
				if (visit[node] < results || results == -1){
					results = visit[node];
				}
			}
			else {
				for (int i = 1; i < N; i++){
					if (matrix[node][i] > 0) {
						if (visit[i] == -1 || visit[i] > matrix[node][i] + visit[node]){
							visit[i] = matrix[node][i] + visit[node];
							enQueue(i);
						}
					}
				}
			}
		}

		if (results == -1) cout << results << endl;
		else {
			jump_long = results/10000;
			jump_short = results%10000;
			cout << jump_long << " " << jump_short << endl;
		}
	}
	return 0;
}


//con ech nhay duong ngan nhat
Editor is loading...
Leave a Comment