백준 11562. 백양로 브레이크

tose33 2023. 4. 13. 15:00

11562번: 백양로 브레이크

서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공

www.acmicpc.net

edge[i][j] 에 i 부터 j 까지 가는데 양방향으로 바꿔야 하는 길의 수 를 저장한다.

따라서 입력을 받을때 (1 2 0) 이라면 1 부터 2 노드 까지 일방통행인 길이 있다는 의미이므로

edge[1][2] = 0

edge[2][1] = 1

이 된다.

(1->2 인 일방통행 길이므로, 1 부터 2 까지는 그냥 갈수 있고, 2 부터 1까지는 해당 길을 양방향으로 바꿔야한다)

이렇게만 해주면 플로이드 와샬 돌려주면 답이 나온다.