Floyd-Warshall1 [BOJ] 11562 백양로 브레이크 이 문제는, 주어진 두 지점에 대해서 '최소 몇번 역방향 다리를 새로 놓아야 접근할 수 있는지' 에 대해 묻는 문제이다. 뒤집어서 생각하는 것이 관건이다. 길이 없는 경우 거리를 무한대, 양방향 길이 있는 경우 거리를 0, 단방향만 있는 경우는 길이 없는 방향에 대해 1 값을 부여한다. 그 후, Floyd-Warshall 알고리즘을 적용하면, 모든 Path에 대해 최단거리로 이동하기 위해 설치해야 할 다리의 갯수가 나온다. #include #include using namespace std; const int INF = 1 2020. 4. 14. 이전 1 다음
