1507번
-
백준 1507번 궁금한 민호 [플로이드] :: 마이구미알고리즘 풀이/그래프 2017. 2. 3. 17:36
이번 글은 백준 알고리즘 문제 "궁금한 민호"를 다뤄본다.플로이드 와샬 알고리즘을 통해 해결한다.백준 알고리즘 1507번 궁금한 민호 - https://www.acmicpc.net/problem/1507 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의..