백준 11404번 플로이드

< 백준 11404번 플로이드 - 마포 코딩박 >

사용한 알고리즘: 플로이드 와샬


 N개의 도시와 도시를 이동하는 버스들의 정보가 주어졌을 때, 임의의 도시 a 에서 도시 b 로 이동하는 비용을 구하는 문제였습니다.
 N이 최대 100으로 작게 주어지고, 각 도시간 이동을 구하는 문제로, 플로이드-와샬로 문제를 해결하였습니다.

풀이는 다음과 같습니다.

(1) (코드 8~9, 14~17)
 'cost[a][b] : a->b 이동하는 비용' 이라고 설정하고, 자기자신으로 이동하는 비용은 0, 나머지는 Infimum 으로 초기화했습니다.

(2) (코드 23~26)
 플로이드와샬은 사실 이 3중 for문으로 끝납니다.
 i->j 갈때, i->k->j 로 중간에 k 들렸다 가는게 작으면 값을 최신화해줍니다.