Problem Solving

X로 그려지는 영역이 3개가 있고, 최소한의 비용으로 이들을 연결해야한다.

뭔가 전반적으로 세팅이 [BOJ 5214 환승](/posts/algorithm/ps/260124_algorithm_boj-5214-%ED%99%98%EC%8A%B9/)이 생각나는 것 같기도?

시작 정점에서 각 출구로 갈 수 있는 최단 경로를 구한 후, 열리는 타이밍에 맞춰 나갈 수 있는 최소 시간을 구하자.

무향그래프고, 정해진 정점중 세개 이상의 정점을 지나야 한다..

일단 가중치가 있는 방향 그래프인데..

무향인 도로와 유향인 웜홀이 있고, 음수 사이클이 있는지를 체크하는 문제이다.

에서 까지 가되, 를 무조건 지니야 한다.

서브태스크가 상당히 많고, 문제가 쉽지 않아보인다. 차근차근 해보자.

일단 인거부터 풀어보자.

생각보다 도 작고, 는 더욱 작다.