Untitled
unknown
plain_text
6 months ago
2.0 kB
20
Indexable
Never
package The_Frog; import java.io.FileInputStream; import java.util.Scanner; public class the_frog { static int MAX_SIZE = 1000; static int [] queue = new int [MAX_SIZE]; static int rear, front; static void push(int x) { if (rear == MAX_SIZE-1) { rear = -1; } rear++; queue[rear] = x; } static int pop() { if (front == MAX_SIZE-1) { front = -1; } front++; return queue[front]; } static boolean isEmpty() { return rear == front; } static int n; static int [][] map; static int [] visit; static int caculate(int i, int j) { int d = (map[0][i] - map[0][j])*(map[0][i] - map[0][j]) + (map[1][i] - map[1][j])*(map[1][i] - map[1][j]); if (d <= (map[2][i] + map[2][j] + 40)*(map[2][i] + map[2][j] + 40)) { return 1; } else if (d <= (map[2][i] + map[2][j] + 90)*(map[2][i] + map[2][j] + 90)) { return 200; } return 100000; } static void bfs(int x) { push(0); visit[0] = 0; while (!isEmpty()) { int a = pop(); for (int i = 0; i < n; i++) { if (i != a) { int b = caculate(a, i); if (visit[i] > visit[a] + b) { visit[i] = visit[a] + b; push(i); } } } } } static void reset() { for (int i = 0; i < n; i++) { visit[i] = 100000; } } public static void main(String[] args) throws Exception{ System.setIn(new FileInputStream("D://Trainee//SRV_training//src//The_Frog//frog.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int test_case = 1; test_case <= T; test_case++) { rear = front = -1; n = sc.nextInt(); map = new int [3][n]; visit = new int [n]; for (int i = 0; i < n; i++) { map[0][i] = sc.nextInt();; map[1][i] = sc.nextInt();; map[2][i] = sc.nextInt();; } reset(); bfs(0); int Ans = visit[n-1]; if (Ans == 100000) { System.out.println(-1); } else { System.out.println((Ans/200) + " " + (Ans%200)); } } } }