https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 다익스트라 알고리즘으로 특정 정점에서 다른 특정 정점까지의 최단거리를 확인하였다. 그렇다면 모든 정점에서 모든 정점으로 가는 최단거리는 어떻게 구할까? 이때 사용하는 알고리즘이 플로이드 워셜이다. 플로이드 워셜은 모든 정점에 대해서 모든 정점으로 가는 최단거리를 중간 지점 노드를 사용하여 계산한다. 음의 간선 사이클이 존재하지 않는다면 음의 가중치를 가진 경우에도..