結果
問題 | No.92 逃走経路 |
ユーザー | tonnnura172 |
提出日時 | 2020-05-08 16:35:08 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,299 bytes |
コンパイル時間 | 1,078 ms |
コンパイル使用メモリ | 86,596 KB |
実行使用メモリ | 128,088 KB |
最終ジャッジ日時 | 2023-09-16 08:30:14 |
合計ジャッジ時間 | 11,044 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 707 ms
128,088 KB |
testcase_01 | AC | 158 ms
80,048 KB |
testcase_02 | AC | 159 ms
80,012 KB |
testcase_03 | AC | 158 ms
79,976 KB |
testcase_04 | AC | 160 ms
80,084 KB |
testcase_05 | AC | 192 ms
82,564 KB |
testcase_06 | AC | 196 ms
83,008 KB |
testcase_07 | AC | 190 ms
83,036 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | TLE | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
ソースコード
import sys, re from collections import deque, defaultdict, Counter from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log from itertools import accumulate, permutations, combinations, product from operator import itemgetter, mul, add from copy import deepcopy from string import ascii_lowercase, ascii_uppercase, digits from bisect import bisect, bisect_left from heapq import heappush, heappop from functools import reduce, lru_cache def input(): return sys.stdin.readline().strip() def INT(): return int(input()) def MAP(): return map(int, input().split()) def LIST(): return list(map(int, input().split())) def ZIP(n): return zip(*(MAP() for _ in range(n))) sys.setrecursionlimit(10 ** 9) INF = float('inf') mod = 10 ** 9 + 7 N, M, K = MAP() abc = [LIST() for _ in range(M)] d = LIST() graph = [[] for _ in range(N)] for a, b, c in abc: graph[a-1].append((b-1, c)) graph[b-1].append((a-1, c)) memo = [[0]*(K+1) for _ in range(N+1)] def DFS(n, step): if memo[n][step]: return True if step == K: ans.add(n+1) return True ret = False for node, w in graph[n]: if step <= M-1 and w == d[step]: if DFS(node, step+1): ret = True memo[n][step] = ret return ret ans = set() for i in range(N): DFS(i, 0) ans = list(ans) print(len(ans)) print(*sorted(ans))