37_플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 happenundo.tistory.com
플로이드
11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제. 플로이드-워셜 알고리즘의 시간복잡도는 O(V^3)인데, 도시 개수가 최대 100개이므로 시간 복잡도도 만족한다. 단, 이 문제에서는 추가된 조건들이 있다. 1. 시작도시와 도착도시가 연결된 노선은 하나가 아닐 수 있다. 2. 마지막에 최단 거리를 출력할 때, 갈 수 없는 경우에는 0을 출력한다. 1번 조건을 만족하기 위해, 이차원 리스트에 거리를 입력할 때, 입력받은 거리가 원래 입력되어 있는 거리보다..
