백준 1507번: 궁금한 민호

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

1507번: 궁금한 민호

 

 

 

 문제 설명 

 

1. 도시의 개수와 각가의 도시사이에 이동하는데 필요한 시간이 주어짐.

2. 필요 없는 도로는 지우고 필요한 최소 도로의 길이를 출력.

 

 알고 리즘 

 

1. 플로이드 알고리즘을 이용해 지워도 되는 도로를 찾아서 지운다.

 

2. 지워도 되는지 여부를 확인하는  알고리즘은 다른 도시를 경유한 시간과 경유하지 않은 시간이 같은경우 경유안한

   경우를 지운다. 

   if (map[i][j] == map[i][k] + map[k][j])del[i][j] = 1;

 

3. 입력된 최소시간이 잘못입력된 경우에 -1을 출력.

 

 

 코 드 

 

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
 
    int N, map[22][22],del[22][22];
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            del[i][j] = 0;
        }
    }
    //플로이드
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
 
                if (i == j || i == k || j == k)continue;
                //지워도 되는 거
                if (map[i][j] == map[i][k] + map[k][j])del[i][j] = 1;
                //모순일경우 -1출력후 종료.
                else if (map[i][j] > map[i][k] + map[k][j]) {
                    cout << -1;
                    return 0;
                }
            }
        }
    }
 
    int result = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (del[i][j] == 1)map[i][j] = 0;            
        }        
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            result += map[i][j];                
        }
    }
    cout << result / 2;
 
}