ABC396Dを解いた【DFS】

筆者はレート800前後の茶～緑コーダ

ABC396当日にACできなかったD問題を解いていく

実装コード

重さを乗せたグラフをつくって深さ優先探索する。

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')


def main():
    N, M = rLI()
    
    G = {i+1:[] for i in range(N)}
    
    for _ in range(M):
        u,v,w = rLI()
        G[u].append((v,w))
        G[v].append((u,w))
    
    visited = set()
    def dfs(v, x, ans):
        visited.add(v)
        if v == N:
            ans = min(ans, x)
        for u, w in G[v]:
            if u not in visited:
                ans = dfs(u, x ^ w, ans)
        visited.remove(v)
        return ans
    
    ans = dfs(1, 0, float('inf'))
    
    print(ans)
    
if __name__ == '__main__':
    main()

まとめ

シンプルな深さ優先探索の問題だけど
メソッドが確立できていない状態で当日を迎えて解けなかったので。
ライブラリ化して素早く実装できるようにしたい。