結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー shin
提出日時 2026-06-27 16:02:01
言語 Java
(openjdk 25.0.2)
コンパイル:
javac -encoding UTF8 _filename_
実行:
java -ea -Xmx700m -Xss256M -DONLINE_JUDGE=true _class_
結果
MLE  
実行時間 -
コード長 2,355 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,942 ms
コンパイル使用メモリ 87,212 KB
実行使用メモリ 714,080 KB
最終ジャッジ日時 2026-06-27 16:02:44
合計ジャッジ時間 11,637 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 MLE * 8 -- * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;

public class No1473 {
	
	static ArrayList<Integer>[] list;
	static long[][] std;
	static int n;

	public static void main(String[] args) throws IOException {
		
		String[] strings = readStr();
		
		n = Integer.parseInt(strings[0].split(" ")[0]);
		int m = Integer.parseInt(strings[0].split(" ")[1]);
		
		std = new long[n+1][m+1];
		int s = 0 , t = 0;
		long d = 0;
		ArrayList<Long> dlist = new ArrayList<Long>();
		
		list = new ArrayList[n+1];
		ArrayList<Integer> list0;

		for(int i = 1;i <= m;i++) {
			s = Integer.parseInt(strings[i].split(" ")[0]);
			t = Integer.parseInt(strings[i].split(" ")[1]);
			d = Long.parseLong((strings[i].split(" ")[2]));
			
			if(!dlist.contains(d)) {
				dlist.add(d);
			}
			
			if(s > t) {
				int t2 = t;
				t = s;
				s = t2;
			}
			
			
			if(list[s] == null ) {
				list0 = new ArrayList<Integer>();
				list0.add(t);
				list[s] = list0; 
				std[s][t] = d; 
			}else if(list[s].contains(t)) {
				std[s][t] = Math.max(d, std[s][t]); 
			}else {
				list[s].add(t);
				list[s].sort(null);
				std[s][t] = d; 
			}

		}
		
		dlist.sort(Collections.reverseOrder());
		
		int count = 0;
		long dans = 0;
		for (long d2 : dlist) {
			count = dhantei(d2);
			if(count > 0) {
				dans = d2;
				break;
			}
		}
		
		System.out.println(dans + " " + count);

		
	}
	
	public static int dhantei(long d) {
	
		int[] root = new int[n+1];
		
		Queue<Integer> queue = new ArrayDeque<Integer>();
		queue.add(1);
		
		while(!queue.isEmpty()) {
			int s = queue.poll();
			
			if(list[s] != null) {
				for (int  t : list[s]) {
					
					if(std[s][t] < d) {
						continue;
					}
					
					if(root[t] == 0) {
						root[t]= root[s] + 1;  
					}else if(root[s] + 1 < root[t]){
						root[t]= root[s] + 1;  
					}
					queue.add(t);
				}
			}
		}
		
		return root[n];
	}
	
	public static String[] readStr() throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		ArrayList<String> list = new ArrayList<>();

		do {
			list.add(br.readLine());
		}while(br.ready());

		br.close();

		String[] text = new String[list.size()];
		list.toArray(text);

		return text;

	}

}
0