#59903 (Java) No.92 逃走経路

• 問題: No.92 逃走経路
• ユーザー: Grenache
• 提出日時: 2015-11-23 11:47:36
• 言語: Java (openjdk 23)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 2,159 bytes
• コンパイル時間: 3,763 ms
• コンパイル使用メモリ: 81,044 KB
• 実行使用メモリ: 110,640 KB
• 最終ジャッジ日時: 2024-09-13 17:14:54
• 合計ジャッジ時間: 14,623 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 10 TLE * 1 -- * 7

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class Main_yukicoder92 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        List<Queue<Edge>> edges = new ArrayList<Queue<Edge>>();
        for (int i = 0; i < n; i++) {
            edges.add(new ArrayDeque<Edge>());
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            int c = sc.nextInt();
            edges.get(a).add(new Edge(a, b, c));
            edges.get(b).add(new Edge(b, a, c));
        }
        int[] d = new int[k];
        for (int i = 0; i < k; i++) {
            d[i] = sc.nextInt();
        }
        Set<Integer> ret = new TreeSet<Integer>();
        for (int i = 0; i < n; i++) {
            Deque<Integer> sts = new ArrayDeque<Integer>();
            Deque<Integer> std = new ArrayDeque<Integer>();
            Deque<Integer> stn = new ArrayDeque<Integer>();
            sts.push(i);
            std.push(0);
            stn.push(i);
            while (!sts.isEmpty()) {
                int st = sts.pop();
                int di = std.pop();
                int no = stn.pop();
                if (di == k) {
                    ret.add(st);
                    break;
                }
                for (Edge e : edges.get(no)) {
                    if (e.w == d[k - 1 - di]) {
                        sts.push(st);
                        std.push(di + 1);
                        stn.push(e.v);
                    }
                }
            }
        }
        System.out.println(ret.size());
        boolean flag = false;
        for (int e : ret) {
            if (!flag) {
                System.out.printf("%d", e + 1);
                flag = true;
            } else {
                System.out.printf(" %d", e + 1);
            }
        }
        System.out.println("");
        sc.close();
    }
    private static class Edge {
//      int u; // from
        int v; // to
        int w; // cost
        Edge(int u, int v, int w) {
//          this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX