結果

問題 No.3482 Quod Erat Demonstrandum
コンテスト
ユーザー ks2m
提出日時 2026-03-27 22:44:44
言語 Java
(openjdk 25.0.2)
コンパイル:
javac -encoding UTF8 _filename_
実行:
java -ea -Xmx700m -Xss256M -DONLINE_JUDGE=true _class_
結果
AC  
実行時間 964 ms / 2,000 ms
コード長 2,165 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,358 ms
コンパイル使用メモリ 85,492 KB
実行使用メモリ 85,924 KB
最終ジャッジ日時 2026-03-27 22:45:21
合計ジャッジ時間 35,840 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		PrintWriter pw = new PrintWriter(System.out);
		for (int z = 0; z < t; z++) {
			String[] sa = br.readLine().split(" ");
			int n = Integer.parseInt(sa[0]);
			int m = Integer.parseInt(sa[1]);
			List<List<Hen>> list = new ArrayList<>(n);
			for (int i = 0; i < n; i++) {
				list.add(new ArrayList<>());
			}
			for (int i = 0; i < m; i++) {
				sa = br.readLine().split(" ");
				int a = Integer.parseInt(sa[0]) - 1;
				int b = Integer.parseInt(sa[1]) - 1;
				int c = Integer.parseInt(sa[2]);
				list.get(a).add(new Hen(b, c));
				list.get(b).add(new Hen(a, c));
			}

			Queue<Integer> que = new ArrayDeque<>();
			que.add(0);
			int[][] d = new int[2][n];
			Arrays.fill(d[0], -1);
			Arrays.fill(d[1], -1);
			d[0][0] = 0;
			while (!que.isEmpty()) {
				int cur = que.poll();
				int cx = cur / n;
				int cy = cur % n;
				for (Hen h : list.get(cy)) {
					if (h.c == 1) {
						if (cx == 0) {
							if (d[0][h.v] == -1) {
								que.add(h.v);
								d[0][h.v] = d[cx][cy] + 1;
							}
						} else {
							if (d[1][h.v] == -1) {
								que.add(n + h.v);
								d[1][h.v] = d[cx][cy] + 1;
							}
						}
					} else {
						if (cx == 0) {
							if (d[1][h.v] == -1) {
								que.add(n + h.v);
								d[1][h.v] = d[cx][cy] + 1;
							}
						}
					}
				}
			}

			if (d[0][n - 1] == -1) {
				if (d[1][n - 1] == -1) {
					pw.println("Unknown");
				} else {
					pw.println("Different");
					pw.println(d[1][n - 1]);
				}
			} else {
				if (d[1][n - 1] == -1) {
					pw.println("Same");
					pw.println(d[0][n - 1]);
				} else {
					throw new RuntimeException();
				}
			}
		}
		pw.flush();
		br.close();
	}

	static class Hen {
		int v, c;

		public Hen(int v, int c) {
			this.v = v;
			this.c = c;
		}
	}
}
0