ABC168 D - .. (Double Dots)
備忘録
問題
回答
import sys sys.setrecursionlimit(10000000) import os import math import bisect import collections import itertools import heapq import re import queue # import fractions ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: (x * y) // math.gcd(x, y) # lcm = lambda x, y: (x * y) // fractions.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, M = il() AB = {m + 1: [] for m in range(M+1)} for _ in range(M): a, b = il() AB[a].append(b) AB[b].append(a) visit = [0] * (N + 1) fifoqu = queue.Queue() fifoqu.put(1) while not fifoqu.empty(): now = fifoqu.get() next = AB[now] for n in next: if visit[n] != 0: continue visit[n] = visit[now] + 1 fifoqu.put(n) else: if visit[1] == 0: print('No') exit() else: visit[1] = 0 print('Yes') for n in range(2, N + 1): deep = visit[n] rooms = AB[n] for room in rooms: if visit[room] == deep - 1: print(room) break if __name__ == '__main__': main()
考え方
部屋1
を起点にして、幅優先探索を行う。
部屋1
から1回の移動で到達できる全ての部屋に1
,2回の移動で到達できる全ての部屋に2
, ...
と、全ての部屋に対して1
からの距離を求めておく。
その後、全ての部屋に対して、部屋1
から自身の部屋に到達するまでに必要な移動数より、
一つ小さい部屋を探し、その部屋を次の部屋への道しるべとする。
例えば、部屋1
から部屋A
に到達するまでに必要な移動回数がN
回のとき、
部屋A
から1回の移動で到達できる部屋の中から、
部屋1
からN-1
回の移動で到達することが出来る部屋B
が部屋A
にとっての最短ルートとなる。