Untitled

 avatar
unknown
plain_text
a year ago
1.3 kB
7
Indexable
#include<iostream>
using namespace std;
int a[200];
int b[200];
int c[200];
int visited[200];
int dis[200];
int n, max;
int count1, count2;
int tinhkhoangcach(int x1, int x2){
	if((40+c[x1]+c[x2])*(40+c[x1]+c[x2])>=((a[x1]-a[x2])*(a[x1]-a[x2])+(b[x1]-b[x2])*(b[x1]-b[x2]))) return 1;
	else if((90+c[x1]+c[x2])*(90+c[x1]+c[x2])>=((a[x1]-a[x2])*(a[x1]-a[x2])+(b[x1]-b[x2])*(b[x1]-b[x2]))) return 200;
	return 1000000;
}
void search(int x, int step){
	//if(x==n-1) return;
	if(step== n-1) return;
	for(int i=0; i<n; i++){
		if(i!=x){
			int h = tinhkhoangcach(x, i);
			if((dis[x]+h)<dis[i])
			dis[i] = dis[x]+h;	
		}
	}
	int min = 1000000;
	int g=0;
	for(int i=1; i<n; i++){
		if(dis[i]<min && visited[i]==0){
			min = dis[i];
			g = i;
		}
	}
	if(g>0){
		visited[g]=1;
		search(g,step+1);
	}
}
int main(){
	//freopen("in.txt","r", stdin);
	int t;
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		cin>>n;
		
		for(int i=0; i<n; i++){
			cin>>a[i]>>b[i]>>c[i];
			dis[i] = 1000000;
			visited[i] = 0;
		}
		dis[0] = 0;
		count1 = 0; count2=0;
		int result=0;
		visited[0] = 1;
		search(0,0);
		if(dis[n-1]==1000000) cout<<"-1"<<endl;
		else
		cout<<dis[n-1]/200<<" "<<dis[n-1]%200<<endl;
	}
	return 0;
}
Editor is loading...