운동
-
[Python] 백준 1956 운동알고리즘/문제풀이 2021. 8. 14. 20:17
1. 문제 링크 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 2. 문제 요약 최소 사이클의 도로 길이의 합을 출력한다. 3. 아이디어 정리 모든 정점에서 모든 정점으로 가는 최소 거리 구하기 ⇒ 플로이드 와샬 자기 자신 -> 자기 자신 마을로 돌아오는 거리 중 최솟값 구하기 참고 - 플로이드와샬 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜 점화식 각 단계마다 특정한 노드 k..