結果

問題 No.168 ものさし
ユーザー uafr_csuafr_cs
提出日時 2015-09-15 00:28:06
言語 Java21
(openjdk 21)
結果
AC  
実行時間 236 ms / 2,000 ms
コード長 2,250 bytes
コンパイル時間 3,125 ms
コンパイル使用メモリ 76,496 KB
実行使用メモリ 60,908 KB
最終ジャッジ日時 2023-08-25 20:59:31
合計ジャッジ時間 8,323 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 220 ms
60,908 KB
testcase_01 AC 123 ms
55,776 KB
testcase_02 AC 124 ms
55,728 KB
testcase_03 AC 123 ms
55,880 KB
testcase_04 AC 122 ms
55,688 KB
testcase_05 AC 122 ms
55,764 KB
testcase_06 AC 124 ms
55,928 KB
testcase_07 AC 124 ms
56,000 KB
testcase_08 AC 121 ms
55,960 KB
testcase_09 AC 143 ms
56,108 KB
testcase_10 AC 157 ms
55,640 KB
testcase_11 AC 213 ms
59,036 KB
testcase_12 AC 225 ms
59,632 KB
testcase_13 AC 236 ms
59,660 KB
testcase_14 AC 200 ms
58,284 KB
testcase_15 AC 123 ms
54,368 KB
testcase_16 AC 146 ms
55,712 KB
testcase_17 AC 154 ms
56,216 KB
testcase_18 AC 177 ms
55,824 KB
testcase_19 AC 232 ms
59,252 KB
testcase_20 AC 228 ms
59,304 KB
testcase_21 AC 235 ms
58,580 KB
testcase_22 AC 234 ms
59,012 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