devbelly

문제 www.acmicpc.net/problem/11562 알고리즘 floyd-warshall 풀이 $u$에서 $v$로 갈 때 필요한 최소한의 다리 설치 수를 묻고 있습니다. 플로이드-와샬의 특징은 모든 출발지와 도착지에 대해 최단거리를 구할 수 있습니다. 문제의 특징과 잘 맞으며 더군다나 $n$ 제한에서 플로이드-와샬임을 느낄 수 있습니다. 처음 모든 $dist$를 큰 값으로 초기화합니다. 만약 양방향 도로가 주어진다면 $dist[u][v]$, $dist [v][u]$를 0으로 설정합니다. 이는 각 정점에서 다른 정점으로 가기 위한 최소한의 다리 설치를 의미합니다. (단, 다리 설치는 단방향 다리에만 추가적으로 설치할 수 있습니다). 반면 단방향 도로가 주어진다면 연결되지 않은 곳만 1로 업데이트해주면..