結果

問題 No.92 逃走経路
コンテスト
ユーザー spacia
提出日時 2016-01-21 23:06:54
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,944 bytes
コンパイル時間 2,265 ms
コンパイル使用メモリ 81,136 KB
実行使用メモリ 84,544 KB
最終ジャッジ日時 2024-09-21 14:58:00
合計ジャッジ時間 14,962 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

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];
		}
		line = br.readLine().split(" ");
		for (int i = 0; i < k; i++) usedMoney[i] = Integer.parseInt(line[i]);
		
		solve();
	}
}
0