結果

問題 No.168 ものさし
ユーザー uafr_csuafr_cs
提出日時 2015-09-15 00:33:44
言語 Java21
(openjdk 21)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 2,027 bytes
コンパイル時間 3,033 ms
コンパイル使用メモリ 74,668 KB
実行使用メモリ 59,628 KB
最終ジャッジ日時 2023-08-25 21:00:10
合計ジャッジ時間 7,476 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 219 ms
58,964 KB
testcase_01 AC 124 ms
55,844 KB
testcase_02 AC 125 ms
55,652 KB
testcase_03 AC 125 ms
55,668 KB
testcase_04 AC 123 ms
55,660 KB
testcase_05 AC 124 ms
55,852 KB
testcase_06 AC 127 ms
55,968 KB
testcase_07 AC 123 ms
55,780 KB
testcase_08 AC 121 ms
55,908 KB
testcase_09 AC 139 ms
56,032 KB
testcase_10 AC 158 ms
55,800 KB
testcase_11 AC 213 ms
59,276 KB
testcase_12 AC 223 ms
58,812 KB
testcase_13 AC 233 ms
58,872 KB
testcase_14 AC 198 ms
58,788 KB
testcase_15 AC 131 ms
56,052 KB
testcase_16 AC 141 ms
56,176 KB
testcase_17 AC 149 ms
55,948 KB
testcase_18 AC 182 ms
53,968 KB
testcase_19 AC 226 ms
59,380 KB
testcase_20 AC 219 ms
59,456 KB
testcase_21 AC 247 ms
58,992 KB
testcase_22 AC 237 ms
59,628 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