Jonyo Programming

[BOJ 1956(G4)리뷰] 문제를 요약하면 사이클이 있는 경로 중 최단경로를 찾으면 된다. 시작점과 도착점을 특정한 상태에서 최단거리를 구할 수 없으므로, 플로이드-와샬 알고리즘을 통해 모든 노드 간의 최단거리를 구한다. 알고리즘을 수행한 후에 dist[i][j]는 i노드에서 j노드까지의 최단거리가 된다. 문제에서 사이클이 존재해야 한다고 했으므로 dist[i][j]와 dist[j][i]가 모두 존재해야 한다. 즉, 'i번 노드에서 j번노드까지의 최단거리 + j번 노드에서 i번 노드까지의 최단거리' 중 가장 작은값이 정답이 될 것이다. /* 21.02.05 BOJ : 1956 운동 (https://www.acmicpc.net/problem/1956) 플로이드-와샬 알고리즘 */ #include usi..