2645: 회로배치

"조금 특이한 점이 있는 문제여서 tistory에서 다뤄보겠다"
고 적었던 tistory 포스트인데 통일성이 없길래 여기로 옮겨왔다.

BFS에서 방문 노드를 queue에다가 집어넣는데, 이 문제는 이를 응용하여 priority queue에 담는다.

그런데 여기서 의문이 생긴다.

"아니, 그거는 걍 다익스트라 아님?" "뭐가 다른거지?"

약간 다르다.

다음은 BFS+Priority Queue 코드이다.

그리고 다음은 Dijkstra 코드이다.

근데 BFS는 $O(n\log n+m)$ 정도? 다익은 $O(n+m\log m)$이니까

거기서 거긴 것도 같은데,

저거 BFS+Priority Queue로 푸는거는 조건이 "가중치의 종류가 2개"라서...

실용적이지도 않다.

가령,

이런 형태는 걍 망한다.

또,

이런 경우도 망한다.

이 문제의 특성상 저런 경우가 존재하지 않아 가능한 것인데,

이런 경우를 다 따지는 것보다는 다익스트라 돌리는게 실용적일 것 같다.