Untitled

mail@pastecode.io avatar
unknown
plain_text
21 days ago
1.5 kB
2
Indexable
Never
#include<iostream>

using namespace std;

int t,n,x,y,r;
int toado[201][3];
int mang[201][201];
int key[201],parent[201],visited[201];

int dis(int i, int j){
	int sum;
	sum=(toado[i][0]-toado[j][0])*(toado[i][0]-toado[j][0])+(toado[i][1]-toado[j][1])*(toado[i][1]-toado[j][1]);
	if(sum<(40+toado[i][2]+toado[j][2])*(40+toado[i][2]+toado[j][2])) return 1;
	else if((sum>(40+toado[i][2]+toado[j][2])*(40+toado[i][2]+toado[j][2])) && (sum<=(90+toado[i][2]+toado[j][2])*(90+toado[i][2]+toado[j][2])) ) return 200;
	else return 2000000;
}

int minKey(){
	int min=1000000;
	int index=0;
	for(int i=1; i<=n; i++){
		if(key[i]<min && visited[i]==0){
			min=key[i];
			index=i;
		}
	}
	return index;
}

void dijkstra(int start){
	for(int i=1; i<=n; i++){
		key[i]=1000000;
		parent[i]=-1;
		visited[i]=0;
	}
	key[start]=0;
	for(int i=1; i<=n; i++){
		int u = minKey();
		visited[u]=1;
		for(int j=1; j<=n; j++){
			if( visited[j]==0){
				if(mang[u][j]+key[u]<key[j]){
					key[j]=mang[u][j]+key[u];
					parent[j]=u;
				}
			}
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> t;
	for(int tc=1;tc<=t;tc++){
		cin >> n;
		for(int i=1;i<=n;i++) {
			cin >> x >> y >> r;
			toado[i][0]=x; toado[i][1]=y; toado[i][2]=r;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) mang[i][j]=dis(i,j);
		}
		dijkstra(1);
		if(visited[n]==0) cout << "-1" << endl;
		else{
			int l=key[n]/200;
			int s=key[n]%200;
			cout << l << " " << s << endl;
		}
	}

	return 0;
}
Leave a Comment