結果

問題 No.168 ものさし
ユーザー uafr_csuafr_cs
提出日時 2015-09-15 00:33:44
言語 Java21
(openjdk 21)
結果
AC  
実行時間 248 ms / 2,000 ms
コード長 2,027 bytes
コンパイル時間 3,957 ms
コンパイル使用メモリ 79,112 KB
実行使用メモリ 45,424 KB
最終ジャッジ日時 2024-06-06 15:03:43
合計ジャッジ時間 7,810 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 221 ms
43,120 KB
testcase_01 AC 133 ms
41,264 KB
testcase_02 AC 128 ms
41,280 KB
testcase_03 AC 132 ms
41,464 KB
testcase_04 AC 132 ms
41,244 KB
testcase_05 AC 132 ms
41,468 KB
testcase_06 AC 134 ms
41,628 KB
testcase_07 AC 136 ms
41,560 KB
testcase_08 AC 119 ms
41,444 KB
testcase_09 AC 141 ms
41,692 KB
testcase_10 AC 161 ms
41,764 KB
testcase_11 AC 211 ms
43,024 KB
testcase_12 AC 235 ms
44,024 KB
testcase_13 AC 248 ms
45,048 KB
testcase_14 AC 205 ms
43,740 KB
testcase_15 AC 134 ms
41,168 KB
testcase_16 AC 156 ms
41,548 KB
testcase_17 AC 157 ms
41,368 KB
testcase_18 AC 176 ms
41,860 KB
testcase_19 AC 239 ms
44,632 KB
testcase_20 AC 237 ms
45,068 KB
testcase_21 AC 242 ms
44,816 KB
testcase_22 AC 232 ms
45,424 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 sqrt = (long)(Math.sqrt(node.max_dist));
				while(sqrt * sqrt < node.max_dist){
					sqrt++;
				}
				System.out.println((sqrt + 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