結果

問題 No.92 逃走経路
ユーザー ぴろず
提出日時 2014-12-07 19:40:42
言語 Java8
(openjdk 1.8.0.222)
結果
AC  
実行時間 205 ms
コード長 1,756 Byte
コンパイル時間 1,971 ms
使用メモリ 25,736 KB
最終ジャッジ日時 2019-09-05 14:45:08

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt AC 184 ms
25,668 KB
sample01.txt AC 113 ms
21,196 KB
sample02.txt AC 115 ms
21,224 KB
test01.txt AC 114 ms
21,232 KB
test02.txt AC 114 ms
21,208 KB
test03.txt AC 192 ms
25,580 KB
test04.txt AC 187 ms
25,588 KB
test05.txt AC 187 ms
25,580 KB
test06.txt AC 153 ms
22,932 KB
test07.txt AC 166 ms
25,704 KB
test08.txt AC 199 ms
25,660 KB
test09.txt AC 199 ms
25,736 KB
test10.txt AC 205 ms
25,676 KB
test11.txt AC 161 ms
24,356 KB
test12.txt AC 164 ms
24,716 KB
test13.txt AC 172 ms
25,628 KB
test14.txt AC 170 ms
25,648 KB
test15.txt AC 184 ms
25,664 KB
test16.txt AC 181 ms
25,656 KB
test17.txt AC 179 ms
25,588 KB
テストケース一括ダウンロード

ソースコード

diff #
package no092;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		Graph g = new Graph(n);
		for(int i=0;i<m;i++) {
			g.addBidirectionalEdge(sc.nextInt()-1, sc.nextInt()-1, sc.nextInt());
		}
		int[] d = new int[k];
		for(int i=0;i<k;i++) {
			d[i] = sc.nextInt();
		}
		boolean[][] dp = new boolean[k+1][n];
		Arrays.fill(dp[0], true);
		for(int i=0;i<k;i++) {
			for(int v=0;v<n;v++) {
				if (!dp[i][v]) {
					continue;
				}
				for(Graph.Edge e:g.graph[v]) {
					if (e.cost == d[i]) {
						dp[i+1][e.to] = true;
					}
				}
			}
		}
		ArrayList<Integer> ans = new ArrayList<>();
		for(int i=0;i<n;i++) {
			if (dp[k][i] == true) {
				ans.add(i+1);
			}
		}
		System.out.println(ans.size());
		for(int i=0;i<ans.size();i++) {
			if (i > 0) {
				System.out.print(" ");
			}
			System.out.print(ans.get(i));
		}
		System.out.println();
	}

}
class Graph {
	public static final int INF = 1<<29;
	int n;
	ArrayList<Edge>[] graph;

	@SuppressWarnings("unchecked")
	public Graph(int n) {
		this.n = n;
		this.graph = new ArrayList[n];
		for(int i=0;i<n;i++) {
			graph[i] = new ArrayList<Edge>();
		}
	}

	public void addBidirectionalEdge(int from,int to,int cost) {
		addEdge(from,to,cost);
		addEdge(to,from,cost);
	}
	public void addEdge(int from,int to,int cost) {
		graph[from].add(new Edge(to, cost));
	}

	class Edge {
		int to;
		int cost;
		public Edge(int to,int cost) {
			this.to = to;
			this.cost = cost;
		}
	}

}
0