結果

問題 No.168 ものさし
ユーザー uafr_csuafr_cs
提出日時 2015-09-15 00:28:06
言語 Java21
(openjdk 21)
結果
AC  
実行時間 231 ms / 2,000 ms
コード長 2,250 bytes
コンパイル時間 2,019 ms
コンパイル使用メモリ 80,780 KB
実行使用メモリ 45,312 KB
最終ジャッジ日時 2024-06-06 15:02:52
合計ジャッジ時間 6,545 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 205 ms
43,476 KB
testcase_01 AC 116 ms
41,204 KB
testcase_02 AC 120 ms
41,188 KB
testcase_03 AC 117 ms
41,068 KB
testcase_04 AC 115 ms
41,148 KB
testcase_05 AC 104 ms
39,896 KB
testcase_06 AC 120 ms
41,456 KB
testcase_07 AC 104 ms
40,072 KB
testcase_08 AC 121 ms
41,076 KB
testcase_09 AC 131 ms
41,720 KB
testcase_10 AC 147 ms
41,588 KB
testcase_11 AC 183 ms
43,716 KB
testcase_12 AC 204 ms
44,372 KB
testcase_13 AC 219 ms
45,292 KB
testcase_14 AC 196 ms
43,784 KB
testcase_15 AC 111 ms
40,144 KB
testcase_16 AC 131 ms
41,596 KB
testcase_17 AC 142 ms
41,508 KB
testcase_18 AC 174 ms
42,396 KB
testcase_19 AC 226 ms
45,312 KB
testcase_20 AC 208 ms
44,580 KB
testcase_21 AC 231 ms
44,648 KB
testcase_22 AC 222 ms
45,276 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

public class Main {
	
	public static class Node implements Comparable<Node> {
		int node;
		long max_dist;
		
		public Node(int node, long max_dist){
			this.node = node;
			this.max_dist = max_dist;
		}

		@Override
		public int compareTo(Node o) {
			return Long.compare(this.max_dist, o.max_dist);
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		long[] xs = new long[N];
		long[] ys = new long[N];
		for(int i = 0; i < N; i++){
			xs[i] = sc.nextLong();
			ys[i] = sc.nextLong();
		}
		
		long[] dists = new long[N];
		Arrays.fill(dists, Long.MAX_VALUE);
		PriorityQueue<Node> queue = new PriorityQueue<Node>();
		queue.add(new Node(0, 0));
		
		while(!queue.isEmpty()){
			final Node node = queue.poll();
			
			if(dists[node.node] < node.max_dist){
				continue;
			}else{
				dists[node.node] = node.max_dist;
			}
			
			if(node.node == N - 1){
				
				long lower = 0, upper = Integer.MAX_VALUE;
				while(lower + 1 < upper){
					final long mid = (lower + upper) / 2;
					
					final long mid_val = mid * mid;
					//System.out.println(upper + " " + lower + " " + mid_val);
					
					if(mid_val >= node.max_dist){
						upper = mid;
					}else{
						lower = mid;
					}
				}
				System.out.println((upper + 9) / 10 * 10);
				
				//System.out.println(node.max_dist);
				//System.out.println((int)(Math.floor(Math.sqrt(node.max_dist))));
				//System.out.println(((int)(Math.sqrt(node.max_dist)) + 9) / 10 * 10);
				break;
			}
			
			final long node_x = xs[node.node];
			final long node_y = ys[node.node];
			
			for(int next = 0; next < N; next++){
				if(node.node == next){ continue; }
				
				final long next_x = xs[next];
				final long next_y = ys[next];
				
				final long next_dist = (node_x - next_x) * (node_x - next_x) + (node_y - next_y) * (node_y - next_y);
				final long next_max = Math.max(next_dist, node.max_dist);
				
				if(dists[next] <= next_max){
					continue;
				}else{
					dists[next] = next_max;
					queue.add(new Node(next, next_max));
				}
			}
		}
		
		
	}

}
0