https://www.acmicpc.net/problem/11404

플로이드 알고리즘은 D[i][j]를 i에서 j로 갈 수 있는 최소비용이라고 할 때,

중간에 도시를 거치지 않고 i에서 j로 갈 수 있는 최소비용,

중간에 도시를 1번 거쳐서 i에서 j로 갈 수 있는 최소비용,

중간에 도시를 2번 거쳐서 i에서 j로 갈 수 있는 최소비용,

.

.

.

중간에 도시를 N번 거쳐서 i에서 j로 갈 수 있는 최소비용을 D[i][j]에 저장해 최종적으로 임의의 도시에서 임의의 도시로 가는 최소비용을 구해내는 알고리즘입니다. 그래프가 directed이든 undirected이든, 그리고 음수인 edge가 있든 없든 아무런 상관이 없지만 edge의 값의 합이 음수인 cycle이 존재하지 않아야 합니다. 시간복잡도는 O(N^3)입니다.

https://github.com/encrypted-def/BOJ/blob/master/11404.cpp