結果
問題 | No.92 逃走経路 |
ユーザー | 双六 |
提出日時 | 2020-07-24 19:49:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 297 ms / 5,000 ms |
コード長 | 1,289 bytes |
コンパイル時間 | 425 ms |
コンパイル使用メモリ | 87,048 KB |
実行使用メモリ | 138,180 KB |
最終ジャッジ日時 | 2023-09-08 01:25:41 |
合計ジャッジ時間 | 4,986 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 179 ms
97,364 KB |
testcase_01 | AC | 93 ms
71,404 KB |
testcase_02 | AC | 93 ms
71,984 KB |
testcase_03 | AC | 92 ms
71,900 KB |
testcase_04 | AC | 93 ms
71,720 KB |
testcase_05 | AC | 239 ms
138,180 KB |
testcase_06 | AC | 117 ms
78,124 KB |
testcase_07 | AC | 113 ms
78,044 KB |
testcase_08 | AC | 106 ms
79,256 KB |
testcase_09 | AC | 142 ms
94,120 KB |
testcase_10 | AC | 229 ms
110,044 KB |
testcase_11 | AC | 232 ms
101,884 KB |
testcase_12 | AC | 297 ms
129,120 KB |
testcase_13 | AC | 143 ms
85,916 KB |
testcase_14 | AC | 171 ms
97,332 KB |
testcase_15 | AC | 189 ms
99,352 KB |
testcase_16 | AC | 177 ms
97,468 KB |
testcase_17 | AC | 168 ms
97,356 KB |
testcase_18 | AC | 148 ms
83,276 KB |
testcase_19 | AC | 138 ms
79,844 KB |
ソースコード
import sys; input = sys.stdin.buffer.readline sys.setrecursionlimit(10**7) from collections import defaultdict from collections import deque INF = float("inf") def getlist(): return list(map(int, input().split())) class Graph(object): def __init__(self): self.graph = defaultdict(list) def __len__(self): return len(self.graph) def add_edge(self, a, b): self.graph[a].append(b) class BFS(object): def __init__(self, graph, s, N): self.g = graph.graph self.Q = deque(); self.Q.append(s) self.dist = [INF] * N; self.dist[s] = 0 while self.Q: v = self.Q.popleft() for i in self.g[v]: if self.dist[i] == INF: self.dist[i] = self.dist[v] + 1 self.Q.append(i) #処理内容 def main(): N, M, K = getlist() G = Graph() E = [] for i in range(M): a, b, c = getlist() a -= 1; b -= 1 E.append([a, b, c]) move = getlist() for a, b, c in E: for j in range(K): if move[j] == c: G.add_edge(a + N * j, b + N * (j + 1)) G.add_edge(b + N * j, a + N * (j + 1)) for i in range(N): G.add_edge(N * (K + 1), i) BF = BFS(G, N * (K + 1), (K + 1) * N + 1) dist = BF.dist ans = 0 ansl = [] for i in range(N): if dist[K * N + i] != INF: ans += 1 ansl.append(i + 1) print(ans) print(*ansl) if __name__ == '__main__': main()