結果
問題 | No.92 逃走経路 |
ユーザー | 👑 はまやんはまやん |
提出日時 | 2015-06-24 16:14:07 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 250 ms / 5,000 ms |
コード長 | 1,400 bytes |
コンパイル時間 | 2,031 ms |
コンパイル使用メモリ | 75,144 KB |
実行使用メモリ | 60,572 KB |
最終ジャッジ日時 | 2023-09-22 00:31:14 |
合計ジャッジ時間 | 7,523 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 237 ms
59,592 KB |
testcase_01 | AC | 122 ms
56,340 KB |
testcase_02 | AC | 123 ms
55,788 KB |
testcase_03 | AC | 123 ms
56,120 KB |
testcase_04 | AC | 123 ms
55,936 KB |
testcase_05 | AC | 244 ms
60,096 KB |
testcase_06 | AC | 220 ms
59,588 KB |
testcase_07 | AC | 222 ms
59,436 KB |
testcase_08 | AC | 188 ms
59,248 KB |
testcase_09 | AC | 213 ms
59,188 KB |
testcase_10 | AC | 241 ms
60,512 KB |
testcase_11 | AC | 236 ms
59,648 KB |
testcase_12 | AC | 250 ms
60,572 KB |
testcase_13 | AC | 200 ms
58,832 KB |
testcase_14 | AC | 208 ms
58,952 KB |
testcase_15 | AC | 211 ms
59,252 KB |
testcase_16 | AC | 214 ms
59,168 KB |
testcase_17 | AC | 232 ms
59,628 KB |
testcase_18 | AC | 217 ms
59,488 KB |
testcase_19 | AC | 211 ms
59,076 KB |
ソースコード
import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; import java.util.TreeSet; public class Main { static int N, M, K; static int[] A, B, C; static int[] D; public static int solve(){ int[][] dp = new int[K+1][N+1]; for (int i = 0; i < K+1; i++) { for (int j = 0; j < N+1; j++) { dp[i][j] = 0; } } for (int i = 0; i < M; i++) { if(C[i] == D[1]) dp[1][A[i]] = dp[1][B[i]] = 1; } for (int k = 2; k <= K; k++) { for (int i = 0; i < M; i++) { if(C[i] == D[k]) { if(dp[k-1][A[i]] == 1) dp[k][B[i]] = 1; if(dp[k-1][B[i]] == 1) dp[k][A[i]] = 1; } } } TreeSet<Integer> ret = new TreeSet<Integer>(); for (int i = 1; i <= N; i++) { if(dp[K][i] == 1) ret.add(new Integer(i)); } System.out.println(ret.size()); int count = 0; for (Integer i : ret) { System.out.print(i); count++; if(count != ret.size()) System.out.print(" "); } System.out.print("\n"); return 0; } public static void main(String[] args){ Scanner S = new Scanner(System.in); N = S.nextInt(); M = S.nextInt(); K = S.nextInt(); A = new int[M]; B = new int[M]; C = new int[M]; for (int i = 0; i < M; i++) { A[i] = S.nextInt(); B[i] = S.nextInt(); C[i] = S.nextInt(); } D = new int[K+1]; for (int i = 1; i < K+1; i++) { D[i] = S.nextInt(); } solve(); } }