알고리즘/최단 경로 구하기(플로이드 워셜)

11404-백준-플로이드

1. 문제 출처 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 풀이 모든 지점에서 다른 모든 지점까지의 최단경로를 계산하는 문제이다.. 딱 플로이드 워셜(이름부터 플로이드 이다...)을 위한 문제이다. 플로이드 워셜의 점화식을 이용하였다. Dab = min(Dab , Dak +Dka) 이를 코드로 표현하면 다음과 같다. for k in range(n): for a in range(n): for b in range(n): D[a][b] =..