플로이드
-
[Python] 백준 11404 플로이드알고리즘/문제풀이 2022. 1. 8. 22:38
1. 문제 링크 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 문제 요약 a → b로 가는 비용의 최솟값 모두 구하기 3. 아이디어 정리 플로이드 와샬. 모든 정점 최단 거리 구하기 참고 - 플로이드 와샬 💡 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용 플로이드 워셜 점화식 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. a에서 b로 가는 최단 거리, a에서 k를 거쳐 ..