devbelly

문제 www.acmicpc.net/problem/1507 알고리즘 플로이드-와샬 풀이 도시를 잇는 최소한의 다리를 구할 때, 해당 다리들을 지나가는데 걸리는 시간의 총합을 묻는 문제였습니다. 문제에서 제시한 $N$제한이 작기 때문에(400 이하) 일일히 시도해보는 브루트포스를 사용할 수 있습니다. 그 중에서도 플로이드 와샬을 통해 구현하면 간단하게 구현이 가능합니다. 플로이드를 사용하는 중 $k$를 거쳐서 단축되는 도시가 존재한다면, 즉 모순이 발생한다면 -1을 출력하도록 합시다. #include #define rep(i,n) for(int i=0;i N; rep(i, N) rep(j, N) { cin >> dist[i][j]; sum += dist[i][j]; } rep(k, N) rep(i, N) r..