🐶

ABC226 C - Martial artist (Python)

2022/01/30に公開

競技プログラミング

AtCoder

abc

tech

C - Martial artist

最後の修行は必ず行うため、最後の修行に必要な要素を後ろからたどっていく過程のTの総和が答えとなります。

実装はDFSやBFSで行います。

stackに乗せる値はリスト形式の最後の値[N-1]とすることが肝です。
実直にTKAの最後の要素TKA[-1]とすると実装が難しくなり、かつTLEします。

TLEの例
https://atcoder.jp/contests/abc226/submissions/28885174

dfs.py

N = int(input())
TKA = [list(map(int, input().split())) for _ in range(N)]

# いまいる場所をstackに、訪れた場所をvisitedに格納します
stack = [N-1]
visited = [False] * N
visited[-1] = True

ans = 0
while stack:
    # いまいる場所をnowに、次に行く場所をtoとします
    now = stack.pop()
    tka = TKA[now]
    ans += tka[0]
    if tka[1] == 0:
        continue
    for i in range(tka[1]):
        to = tka[i+2]-1
        if not visited[to]:
            visited[to] = True
            stack.append(to)

print(ans)

C - Martial artist

Discussion