Untitled
unknown
plain_text
a month ago
2.3 kB
1
Indexable
Never
package Graph2; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class The_Frog { static int n, minSum = 0; static int minKey(int key[], Boolean visited[]) { int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v < n; v++) if (visited[v] == false && key[v] < min) { min = key[v]; min_index = v; } return min_index; } static void primMST(int arr[][]) { int parent[] = new int[n]; int key[] = new int[n]; Boolean visited[] = new Boolean[n]; for (int i = 0; i < n; i++) { key[i] = Integer.MAX_VALUE; visited[i] = false; } key[0] = 0; parent[0] = -1; for (int count = 0; count < n; count++) { int u = minKey(key, visited); if (u != -1) { visited[u] = true; for (int v = 0; v < n; v++) { if (arr[u][v] == -1) { continue; } if (arr[u][v] + key[u] < key[v]) { parent[v] = u; key[v] = arr[u][v] + key[u]; } } } } if (key[n - 1] == Integer.MAX_VALUE) { System.out.println(-1); } else { int kq1 = key[n - 1] % 1000; int kq2 = key[n - 1] / 1000; System.out.println(kq2 + " " + kq1); } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("Text")); Scanner scanner = new Scanner(System.in); int tc = scanner.nextInt(); for (int Case = 1; Case <= tc; Case++) { n = scanner.nextInt(); int arr[][] = new int[n][n]; int dx[] = new int[n]; int dy[] = new int[n]; int dr[] = new int[n]; for (int i = 0; i < n; i++) { dx[i] = scanner.nextInt(); dy[i] = scanner.nextInt(); dr[i] = scanner.nextInt(); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int x = dx[i] - dx[j]; int y = dy[i] - dy[j]; if (i == j) { arr[i][j] = 0; } else { double kc = Math.sqrt(x * x + y * y) - dr[i] - dr[j]; if (kc <= 40) { arr[i][j] = 1; arr[j][i] = 1; } else if ( kc <= 90) { arr[i][j] = 1000; arr[j][i] = 1000; } else { arr[j][i] = -1; arr[i][j] = -1; } } } } primMST(arr); // System.out.println(minSum); } } }