이동식 저장소

11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 원래 건물을 잇는 모든 길은 양방향이었는데, 공사 때문에 몇몇 길이 일방통행으로 바뀌어 버렸다. 이제 두 건물 사이를 오가려면 일방통행 길을 최소한 몇 개나 양방향으로 바꿔야 하는지 알아보자. 흠.. 그런데 쿼리가 최대 3만 개 주어진다. 매번 길을 탐색하면 시간 초과가 날 것 같다. 따라서 모든 $s,~e$ 쌍에 대해 정답을 미리 구해 놓아야 한다. 풀이 다익스트라 또는 플로이드 와샬 알고리즘으로 풀 수 있다. 두 방법 모두 주어지는 단방향 간선 $u,~v$에..