[1507] 궁금한 민호

https://www.acmicpc.net/problem/1507

별 이상한 방법으로 엄청 시도했습니다..

dfs, bfs, 비트마스크 등등 ㅠㅠㅠㅠ....

해결 알고리즘은 플로이드-와샬을 이용하는 것입니다.

플로이드-와샬을 이용하면 모든 정점에 대한 최단거리를 테이블로 만들 수 있습니다.

잘모르시는 분들은 다른 블로그나 책을 통해서 공부하시고 참고해주시기 바랍니다.

input으로 들어오는 테이블이 현재 최단 거리 테이블이니

그 테이블을 기준으로 다시 한번 플로이드를 돌립니다.

이 때 중요한 것은

i - k - j(i에서 k를 거쳐 j로 가는 거리)가 i - j와 같다면

i - j간선, i - k간선, k-j간선 총 세개가 필요했던 것이

i - k, k - j 두 개의 간선으로 표현이 가능합니다.

플로이드를 통해서 이러한 간선을 전부 체크해준 후에

마지막에 체크되지 않은 간선 / 2 혹은 2차원 테이블에서 반만 더해준 후에 결과를 출력합니다.

-1이 출력되는 조건은 input으로 들어온 데이터가 최단거리가 아닐 때 입니다.

아래는 풀 코드입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 200
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int spend[20][20];
int n;
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> spend[i][j];
        }
    }
 
    bool destroy[20][20] = { 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 || k == j) continue;
                
                //삭제할 간선 찾기
                if (spend[i][j] == spend[i][k] + spend[k][j]) {
                    destroy[i][j] = 1;
                }
                //i, j가 최단거리가 아닐경우 -1 출력
                else if (spend[i][j] > spend[i][k] + spend[k][j]) {
                    puts("-1");
                    return 0;
                }
            }
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            ret += !destroy[i][j] * spend[i][j];
        }
    }
 
    cout << ret;
 
    return 0;
}