Frog - NDDCoder

#include<iostream>
#define NEAR 40
#define FAR 90

using namespace std;
int T;
int n;
int dist[200][200];
int vs[200], d1[200], d2[200];

long long sq(int x){
	return x*x;
}

int calculateNearFar(int x1, int y1, int r1, int x2, int y2, int r2){
	long long tmp_dis = sq(x1-x2)+sq(y1-y2);
//	cout<<"tmpdies "<<tmp_dis<<endl;
//	cout<<sq(r1+r2+40)<<endl;
	if (tmp_dis<=sq(r1+r2+NEAR)) return 1;
	if (tmp_dis<=sq(r1+r2+FAR)) return 2;
	return 0;
}

int main(){
	freopen("Frog.txt","r",stdin);
	cin>>T;
	while(T--){
		cin>>n;
		int a[200][3];
		for (int i=0;i<n;i++){
			cin>>a[i][0]>>a[i][1]>>a[i][2];
			dist[i][i]=0;
		}
		for (int i=0;i<n-1;i++){
			for (int j=i+1;j<n;j++){
				int d = calculateNearFar(a[i][0], a[i][1], a[i][2], a[j][0], a[j][1], a[j][2]);
//				cout<<i<<" "<<j<<" "<<d<<endl;
//				cout<<a[i][0]<<" "<<a[i][1]<<" "<<a[i][2]<<" "<<a[j][0]<<" "<<a[j][1]<<" "<<a[j][2]<<endl;
				dist[i][j]=d;
				dist[j][i]=d;
			}
		}
		// init
		for (int i=0;i<n;i++){
			vs[i]=0;
			d1[i]=-1;
			d2[i]=-1;
//			for (int j=0;j<n;j++){
//				cout<<dist[i][j]<<" ";
//			}
//			cout<<endl;
		}
		d1[0]=0;
		d2[0]=0;
		//
		for (int loop=0;loop<n-1;loop++){
			// find smallest distance vertex
			int n1min=-1, n2min=-1, imin;
			for (int i=0;i<n;i++){
				if (!vs[i] && d1[i]!=-1 && d2[i]!=-1){
//					cout<<i<<" "<<d1[i]<<" "<<d2[i]<<endl;
					if (n1min==-1|| (d2[i]<n2min || (d2[i]==n2min && d1[i]<n1min))){
						n1min=d1[i];
						n2min=d2[i];
						imin=i;
					}
				}
			}
			if (n1min!=-1){
//				cout<<imin<<" "<<n1min<<" "<<n2min<<endl;
				for (int i=0;i<n;i++){
					if (!vs[i] && dist[imin][i]){
						int tmp = dist[imin][i];
						int tmp1 = n1min, tmp2=n2min;
						if (tmp==1) tmp1++;
						else if (tmp==2) tmp2++;
						if (d1[i]==-1 || (tmp2 < d2[i] || (tmp2==d2[i] && tmp1<d1[i]))){
							d1[i]=tmp1;
							d2[i]=tmp2;
						}
					}
				}
				vs[imin]=1;
			}
		}
		if (d1[n-1]==-1) cout<<-1<<endl;
		else cout<<d2[n-1]<<" "<<d1[n-1]<<endl;
	}
}