문제 링크 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N^3) - 플로이드 워셜 공식 활용하여 각 노드별 최단 경로는 구한다 floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j] i -> j로 바로가는 비용과 k 를 거쳐 가는 i -> k -> j 비용 중 작은 값을 구한다 경로 추적 - (1,1) ~ (N, N) 까지 경로 추적하는 부분에서 시작과 끝 ..