Untitled

mail@pastecode.io avatar
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);

		}
	}
}