11562. 백양로 브레이크

11562번: 백양로 브레이크

원래 건물을 잇는 모든 길은 양방향이었는데, 공사 때문에 몇몇 길이 일방통행으로 바뀌어 버렸다. 이제 두 건물 사이를 오가려면 일방통행 길을 최소한 몇 개나 양방향으로 바꿔야 하는지 알아보자.

 

흠.. 그런데 쿼리가 최대 3만 개 주어진다. 매번 길을 탐색하면 시간 초과가 날 것 같다. 따라서 모든 $s,~e$ 쌍에 대해 정답을 미리 구해 놓아야 한다.

풀이

다익스트라 또는 플로이드 와샬 알고리즘으로 풀 수 있다. 두 방법 모두 주어지는 단방향 간선 $u,~v$에 대해 $v$에서 $u$로 가는 간선의 cost를 1로 놓고 거리를 계산하면 된다. 당연히 양방향 간선의 cost는 0이다.

 

플로이드 와샬을 적용하려면 간선이 주어지지 않은 정점 쌍의 거리를 매우 큰 값으로 놓고 계산하면 된다.

---