結果

問題 No.92 逃走経路
ユーザー spacia
提出日時 2016-01-22 20:23:02
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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