Untitled

mail@pastecode.io avatar
unknown
plain_text
6 months ago
2.6 kB
2
Indexable
Never
#include <stdio.h>
#include <iostream>

#define MAX_N 205

using namespace std;
int N;
int leaf[MAX_N][3];
int map[MAX_N][MAX_N];
int visit[MAX_N][2];
int Queue[200000];
int startQ, endQ;

void push(int i){
	Queue[endQ] = i;
	endQ++;
}

void BFS(){
	while (startQ < endQ)
	{
		int k = Queue[startQ];
		startQ ++;
		int jump = visit[k][0];
		int bigJump = visit[k][1];
		for( int i = 1 ; i<= N ; i++){
			if (map[k][i] == 0){
				if ( visit[i][1] > bigJump || ( visit[i][1] == bigJump && visit[i][0] > jump +1 ) ) {
					visit[i][1] = bigJump;
					visit[i][0] = jump +1;
					push(i);
				}
			}
			if (map[k][i] == 1){
				if ( visit[i][1] > bigJump + 1 || ( visit[i][1] == bigJump + 1 && visit[i][0] > jump ) ) {
					visit[i][1] = bigJump + 1;
					visit[i][0] = jump;
					push(i);
				}
			}
		}
	}
}
int main(int argc, char** argv)
{
	int tc, T;
	cin >> T;
	for(tc = 0; tc < T; tc++)
	{
		cin >> N;
		for (int i =1; i<= N; i++){
			visit[i][0] = MAX_N;
			visit[i][1] = MAX_N;
			cin >> leaf[i][0] >> leaf[i][1] >> leaf[i][2];
		}
		for (int i =1; i< N; i++){
			for (int j = i+1; j <= N; j++){
				int squareDistance = (leaf[i][0] - leaf[j][0])  * (leaf[i][0] - leaf[j][0]) + (leaf[i][1] - leaf[j][1])  * (leaf[i][1] - leaf[j][1]) ; 
				if (squareDistance <= ( 40 + leaf[i][2] + leaf[j][2]) * ( 40 + leaf[i][2] + leaf[j][2]) ) {map[i][j] = 0; map[j][i] = 0;}
				else if (squareDistance <= ( 90 + leaf[i][2] + leaf[j][2]) * ( 90 + leaf[i][2] + leaf[j][2]) ) {map[i][j] = 1; map[j][i] = 1;}
				else {map[i][j] = -1; map[j][i] = -1; }
			}
		}
		startQ = 0;
		endQ = 0;
		push(1);
		visit[1][0] = 0;
		visit[1][1] = 0;
		BFS();

		if ( visit[N][0] == MAX_N) 
			cout << -1 << endl;
		else cout << visit[N][1] << " " << visit[N][0] << endl;
	}

	return 0;
}
////////////////////////////////////////////
20
4 6 0 5 1 1
0 1 1 1 0 0
1 1 1 0 0 1
1 0 1 1 0 1
1 1 1 1 1 1

5 4 4 2 0 0
1 0 1 1
1 1 1 0
0 1 0 1
1 1 1 1
1 0 0 1

4 7 1 1 0 5
1 1 0 1 0 0 1
1 0 0 1 1 0 1
0 1 1 1 0 1 1
0 1 1 1 1 1 1

10 10 3 6 3 5
1 0 1 0 1 0 1 0 1 0 
0 1 1 0 1 0 0 0 0 1 
0 0 0 0 1 0 1 0 0 0 
0 0 0 0 0 1 0 0 1 1 
0 1 1 0 1 0 0 0 1 1 
1 1 0 1 1 0 0 0 1 0 
1 0 1 1 0 1 1 1 0 1 
0 0 0 0 1 1 1 1 0 1 
1 0 0 1 1 0 1 0 0 0 
1 1 1 0 0 1 1 0 1 0 

10 10 6 8 1 5
0 1 0 1 0 0 1 0 0 1 
1 0 1 1 1 0 1 0 0 1 
0 0 0 1 1 1 0 1 1 0 
0 0 1 1 1 1 0 0 0 0 
1 1 0 1 0 1 0 0 0 0 
1 1 0 1 0 1 1 1 0 1 
1 0 1 0 0 1 1 1 1 0 
0 1 1 0 0 1 0 0 0 1 
1 1 1 0 0 1 0 0 0 1 
1 0 0 0 0 0 1 1 0 1