Untitled

unknown
plain_text
6 months ago
1.8 kB
1
Indexable
Never
```package the;

import java.util.Scanner;

public class test {
static int N;
static int[][] Energy=new int[1000][1000];
static int[] MinEnergy=new int[1000];
static int[] visit=new int[1000];
static int[] x=new int[1000];
static int[] y=new int[1000];
static int[] r=new int[1000];
static int calEnergy(int x1,int y1,int r1,int x2,int y2,int r2){
if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=(40+r1+r2)*(40+r1+r2)){
return 1;
}
else if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=(90+r1+r2)*(90+r1+r2)){
return 200;
}
return 99999;
}
static void reset(){
for(int i=0;i<N;i++){
visit[i]=0;
MinEnergy[i]=99999;
}

}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int tc=scanner.nextInt();
for(int i=0;i<tc;i++){
N=scanner.nextInt();
for(int j=0;j<N;j++){
x[j]=scanner.nextInt();
y[j]=scanner.nextInt();
r[j]=scanner.nextInt();
}
reset();
for(int j=0;j<N;j++){
for(int k=0;k<N;k++){
if(j==k){
Energy[j][k]=0;
}
else{
Energy[j][k]=calEnergy(x[j], y[j], r[j], x[k], y[k], r[k]);
}
}
}
int selected=0;
MinEnergy[0]=0;
int nearleaf=0,nearDist=0;
while(selected<N){
nearDist=99999;
for(int j=0;j<N;j++){
if(visit[j]==0 && MinEnergy[j]<nearDist){
nearDist=MinEnergy[j];
nearleaf=j;
}
}
if(nearDist==99999 || selected==N-1){
break;
}
selected++;
visit[nearleaf]=1;
for(int j=0;j<N;j++){
if(visit[j]==0 && MinEnergy[nearleaf]+Energy[nearleaf][j]<MinEnergy[j]){
MinEnergy[j]=MinEnergy[nearleaf]+Energy[nearleaf][j];
}
}
}
if(MinEnergy[N-1]==99999){
System.out.println(-1);
}
else {
System.out.println(MinEnergy[N-1]/200 + " "+MinEnergy[N-1]%200);
}

}
}
}
```