結果

問題 No.92 逃走経路
ユーザー spaciaspacia
提出日時 2016-01-22 00:33:58
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,151 bytes
コンパイル時間 2,815 ms
コンパイル使用メモリ 80,080 KB
実行使用メモリ 116,948 KB
最終ジャッジ日時 2024-09-21 14:59:04
合計ジャッジ時間 14,997 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

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 PriorityQueue<Integer> ans = new PriorityQueue<Integer>();
	
	public static void out (Object o) {
		System.out.println(o);
	}
	
	public static void bruteForce (int cnt , int pos) {
		if (cnt == k) {
			ans.add(pos);
			return;
		}
		if (pos == -1) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (memo[i][j] == null) continue;
					String[] s = memo[i][j].split(",");
					for (int k = 0; k < s.length; k++) {
						int l = Integer.parseInt(s[k]);
						if (usedMoney[cnt] == l) bruteForce(cnt + 1 , j);
					}
				}
			}
		} else {
			for (int i = 1; i <= n; i++) {
				if (memo[pos][i] == null) continue;
				String[] s = memo[pos][i].split(",");
				for (int j = 0; j < s.length; j++) {
					int l = Integer.parseInt(s[j]);
					if (usedMoney[cnt] == l) bruteForce(cnt + 1 , i);
				}
			}
		}
	}
	
	public static void solve () {
		bruteForce(0 , -1);
		out(ans.size());
		System.out.print(ans.poll());
		while (!ans.isEmpty()) System.out.print(" " + ans.poll());
		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 k = Integer.parseInt(line[1]);
			memo[j][k] = memo[j][k] == null ? line[2] : memo[j][k] + "," + line[2];
			memo[k][j] = memo[k][j] == null ? line[2] : memo[k][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