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(); } }