백준 1507번 궁금한 민호

문제 링크입니다: https://www.acmicpc.net/problem/1507

플로이드-와샬 알고리즘을 사용하여 최소의 도로를 선택하는 문제였습니다.

플로이드 알고리즘을 적용하여 i에서 j로 가는데 k를 거쳐가는 경우와 같다면 보다 많은 도시를 커버해야하기 때문에 i->j 도로를 선택하지 않고 i->k, k->j 도로를 선택합니다.

반면, i->j로 가는 경로의 길이가 k를 거쳐가는 길이보다 크다면 최소 이동거리가 성립하지 않기 때문에 -1을 출력합니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 20;

 

int N;

int graph[MAX][MAX];

int road[MAX][MAX];

int result;

 

void floyd(void)

{

        for (int k = 0; k < N; k++)

                 for (int i = 0; i < N; i++)

                         for (int j = 0; j < N; j++)

                                 if (i == j || j == k || i == k)

                                          continue;

                                 //플로이드 성립 X(최소 이동시간이 아니다)

                                 else if (graph[i][j] > graph[i][k] + graph[k][j])

                                 {

                                          result = -1;

                                          return;

                                 }

                                 //i->j로 가는 경로가 k를 거쳐가는 경우와 같다면

                                 //모든 경로를 최소의 도로로 커버해야하므로 k를 거쳐가는 도로를 선택한다

                                 else if (graph[i][j] == graph[i][k] + graph[k][j])

                                          road[i][j] = false;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         cin >> graph[i][j];

 

        memset(road, true, sizeof(road));

        floyd();

 

        //-1이면 불가능

        if (result != -1)

                 for (int i = 0; i < N; i++)

                         for (int j = 0; j < N; j++)

                                 if (road[i][j])

                                          result += graph[i][j];

 

        if (result == -1)

                 cout << -1 << endl;

        else

                 //i->j, j->i 둘다 계산했으므로 반으로 나누어준다

                 cout << result / 2 << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~