結果

問題 No.92 逃走経路
ユーザー ぴろず
提出日時 2014-12-07 19:40:42
言語 Java8
(openjdk 1.8.0.191)
結果
AC  
実行時間 188 ms
コード長 1,756 Byte
コンパイル時間 1,475 ms
使用メモリ 37,036 KB
最終ジャッジ日時 2019-06-24 15:19:33

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt AC 175 ms
37,036 KB
sample01.txt AC 108 ms
32,736 KB
sample02.txt AC 106 ms
30,180 KB
test01.txt AC 107 ms
31,904 KB
test02.txt AC 107 ms
32,156 KB
test03.txt AC 188 ms
35,732 KB
test04.txt AC 179 ms
35,052 KB
test05.txt AC 179 ms
35,056 KB
test06.txt AC 138 ms
33,272 KB
test07.txt AC 153 ms
33,556 KB
test08.txt AC 183 ms
35,052 KB
test09.txt AC 187 ms
37,016 KB
test10.txt AC 184 ms
35,856 KB
test11.txt AC 149 ms
34,524 KB
test12.txt AC 154 ms
34,936 KB
test13.txt AC 160 ms
35,056 KB
test14.txt AC 161 ms
35,060 KB
test15.txt AC 172 ms
35,052 KB
test16.txt AC 169 ms
35,052 KB
test17.txt AC 169 ms
33,552 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