結果

問題 No.92 逃走経路
ユーザー spaciaspacia
提出日時 2016-01-22 20:23:02
言語 Java21
(openjdk 21)
結果
AC  
実行時間 785 ms / 5,000 ms
コード長 2,032 bytes
コンパイル時間 3,708 ms
コンパイル使用メモリ 79,836 KB
実行使用メモリ 179,736 KB
最終ジャッジ日時 2023-10-21 13:47:04
合計ジャッジ時間 9,965 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 722 ms
61,172 KB
testcase_01 AC 48 ms
52,548 KB
testcase_02 AC 72 ms
54,416 KB
testcase_03 AC 54 ms
53,668 KB
testcase_04 AC 52 ms
53,672 KB
testcase_05 AC 656 ms
158,020 KB
testcase_06 AC 785 ms
179,736 KB
testcase_07 AC 784 ms
179,676 KB
testcase_08 AC 87 ms
55,872 KB
testcase_09 AC 156 ms
59,536 KB
testcase_10 AC 124 ms
59,664 KB
testcase_11 AC 133 ms
60,852 KB
testcase_12 AC 342 ms
67,500 KB
testcase_13 AC 135 ms
59,744 KB
testcase_14 AC 363 ms
63,456 KB
testcase_15 AC 284 ms
64,044 KB
testcase_16 AC 265 ms
60,720 KB
testcase_17 AC 462 ms
60,804 KB
testcase_18 AC 541 ms
62,088 KB
testcase_19 AC 405 ms
62,092 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package Main;

import java.io.*;
import java.util.*;
import java.math.*;

class Main {
	
	static int n , m , k;
	static int[] usedMoney;
	static String[][] memo;
	static ArrayList<Integer> ans = new ArrayList<Integer>();
        
	public static void out (Object o) {
		System.out.println(o);
	}
	
	public static boolean check (int pos , int cnt) {
            if (cnt == k) return true;
            for (int i = 1; i <= n; i++) {
                if (memo[pos][i] == null) continue;
                String[] s = memo[pos][i].split(",");
                for (String item : s) {
                    int l = Integer.parseInt(item);
                    if (l != usedMoney[k - cnt - 1]) continue;
                    if (check(i , cnt + 1)) return true;
                }
            }
            return false;
	}
	
	public static void solve () {
		for (int i = 1; i <= n; i++)
                    if (check(i , 0)) ans.add(i);
		out(ans.size());
		System.out.print(ans.get(0));
		for (int i = 1; i < ans.size(); i++) System.out.print(" " + ans.get(i));
		out("");
	}
	
	public static void main (String[] args) throws IOException {
		BufferedReader br = 
			new BufferedReader(new InputStreamReader(System.in));
		
		String[] line = br.readLine().split(" ");
		n = Integer.parseInt(line[0]);
		m = Integer.parseInt(line[1]);
		k = Integer.parseInt(line[2]);
		usedMoney = new int[k];
		memo = new String[n + 1][n + 1];
		
		for (int i = 0; i < m; i++) {
			line = br.readLine().split(" ");
			int j = Integer.parseInt(line[0]);
			int l = Integer.parseInt(line[1]);
			memo[j][l] = memo[j][l] == null ? line[2] : memo[j][l] + "," + line[2];
			memo[l][j] = memo[l][j] == null ? line[2] : memo[l][j] + "," + line[2];
		}
		
		String[] line2 = br.readLine().split(" ");
		for (int i = 0; i < k; i++) usedMoney[i] = Integer.parseInt(line2[i]);
		
               // long s = System.currentTimeMillis();
		solve();
                //long e = System.currentTimeMillis();
                
               // out("time : " + (e - s) + "ms");
	}
}
0