# Untitled

unknown
plain_text
a year ago
2.5 kB
2
Indexable
Never
```package The_Frog;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution1 {
static int n, mind = 40, maxd = 90, demp ;
static int[] x, y;
static int res, res1, res2;
static int[] visit;
static int[] r;
static double[] distan, weight;
static int[] path;
static int[][] a;

public static void Dijkstra(int start){
int dinh = start;
int s = 1;
double min = 0;
visit[dinh] = 1;
distan[dinh] = 0;
while( s < n){

for(int i = 0; i < n; i++){
if(visit[i] == 0 && a[dinh][i] > 0){
distan[i] = Math.min( a[dinh][i] + distan[dinh] , distan[i]);
}
}

min = Double.MAX_VALUE;
for(int i = 0; i < n; i++){
if(visit[i] == 0 && distan[i] < min){
min = distan[i];
dinh = i;
}
}

visit[dinh] = 1;

s ++;

}

}

public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

Scanner scanner = new Scanner(System.in);

int test = scanner.nextInt();
for(int t = 1; t <= test; t++){

n = scanner.nextInt();
x = new int[n];
y = new int[n];
visit = new int[n];
distan =  new double[n];
r = new int[n];
for(int i = 0; i < n; i++){
x[i] = scanner.nextInt();
y[i] = scanner.nextInt();
r[i] = scanner.nextInt();
}
for(int i = 0; i < n; i++){
distan[i] = Double.MAX_VALUE;
}
a = new int[n][n];
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
double kc = Math.sqrt(Math.pow(x[i]-x[j], 2) + Math.pow(y[i]-y[j], 2)) - r[i] - r[j];
if(kc <= 40 ){
a[i][j] = 1;
a[j][i] = 1;
}else if(kc <= 90){
a[i][j] = 1000;
a[j][i] = 1000;
}
}
}

//			for(int i = 0; i < n; i++){
//				for(int j = 0; j < n; j++){
//					System.out.print(a[i][j] + " ");
//				}
//				System.out.println();
//			}

Dijkstra(0);

//			for(int i = 0; i < n; i++){
//					System.out.print(distan[i] + " ");
//			}
//			System.out.println();

if(visit[n-1] == 0){
System.out.println(-1);
}else{
System.out.println((int)distan[n-1]/1000 + " " + (int)distan[n-1]%1000);
}

}

scanner.close();
}
}

```