結果

問題 No.168 ものさし
ユーザー uafr_cs
提出日時 2015-09-15 00:33:44
言語 Java
(openjdk 23)
結果
AC  
実行時間 267 ms / 2,000 ms
コード長 2,027 bytes
コンパイル時間 2,875 ms
コンパイル使用メモリ 79,672 KB
実行使用メモリ 45,320 KB
最終ジャッジ日時 2024-12-24 07:12:25
合計ジャッジ時間 8,071 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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