結果

問題 No.92 逃走経路
ユーザー spaciaspacia
提出日時 2016-01-22 20:23:02
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,040 ms / 5,000 ms
コード長 2,032 bytes
コンパイル時間 2,312 ms
コンパイル使用メモリ 80,180 KB
実行使用メモリ 176,548 KB
最終ジャッジ日時 2024-09-21 15:01:35
合計ジャッジ時間 11,885 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 814 ms
50,772 KB
testcase_01 AC 52 ms
36,960 KB
testcase_02 AC 83 ms
38,140 KB
testcase_03 AC 59 ms
37,468 KB
testcase_04 AC 59 ms
37,256 KB
testcase_05 AC 784 ms
145,012 KB
testcase_06 AC 1,040 ms
176,548 KB
testcase_07 AC 967 ms
166,684 KB
testcase_08 AC 97 ms
39,652 KB
testcase_09 AC 183 ms
44,052 KB
testcase_10 AC 139 ms
42,364 KB
testcase_11 AC 152 ms
43,136 KB
testcase_12 AC 406 ms
54,428 KB
testcase_13 AC 155 ms
42,764 KB
testcase_14 AC 414 ms
48,692 KB
testcase_15 AC 338 ms
49,400 KB
testcase_16 AC 313 ms
46,200 KB
testcase_17 AC 538 ms
50,588 KB
testcase_18 AC 634 ms
55,864 KB
testcase_19 AC 677 ms
57,160 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