ABC376Dを解いた【幅優先探索】

筆者はレート700前後の茶色コーダ

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

実装コード

1を起点として幅優先をすればいい
その場合探索したノードの持つ辺に1が繋がっていれば閉路になるので
たどり着くまでの数の最小値比較すればOK

import sys
from collections import deque
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())
def err(*args): print(*args, file=sys.stderr)

def main():
    N, M = rLI()
    G = {i+1:set() for i in range(N)}
    
    for _ in range(M):
        a, b = rLI()
        G[a].add(b)

    v = {i+1:-1 for i in range(N)}
    q = deque([(1, 1)]) 
    m = float('inf')

    while q:
        n, d = q.popleft()
        v[n] = d
        for nb in G[n]:
            if nb == 1:
                # err(p,d+1)
                m = min(m, d)
            if v[nb] == -1:
                q.append((nb, d + 1))

    print(m if m != float('inf') else -1)
    
if __name__ == '__main__':
    main()

まとめ

当日はGPTに投げてすぐ飛ばしてしまったが
そのコードから少し手直しするだけでACができた

出力されたコード全く読まないのは良くないね😅