BOJ 28130 - 슈넬치킨 랑데부

May 31, 2023

지문이 좀 헷갈리는데 BFS 문제이다.

모든 가장자리에 대해서 선우가 도착하는 시점이 $0,1,2,3,4,\dots,e$ 처럼 나올 때, 항상 $2 \mid e$ 이다.

일단 상혁이의 초기 위치부터 모든 곳까지 최단거리를 계산한다.

어떤 가장자리에 대해 상혁이가 $t_2$ 에 도착하고 선우가 $t_1$ 에 도착한다면,

일단 $t_1 \ge t2$ 가 되도록 $t_1 \coloneqq t_1+ke$ 를 해준뒤, $t_1$ 과 $t_2$ 의 parity를 비교해서 parity가 동일하다면 만날 수 있고 그렇지 않다면 만날 수 없다.

만날 수 있을 때의 정답은 $t_1$ 이다.

$2 \mid e$ 이기 때문에 $e$ 는 parity에 영향을 안미치는 점을 유의한다.

You may also enjoy