[백준 1507] 궁금한 민호

문제

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

알고리즘

플로이드-와샬

풀이

도시를 잇는 최소한의 다리를 구할 때, 해당 다리들을 지나가는데 걸리는 시간의 총합을 묻는 문제였습니다.

문제에서 제시한 $N$제한이 작기 때문에(400 이하) 일일히 시도해보는 브루트포스를 사용할 수 있습니다. 그 중에서도 플로이드 와샬을 통해 구현하면 간단하게 구현이 가능합니다.

플로이드를 사용하는 중 $k$를 거쳐서 단축되는 도시가 존재한다면, 즉 모순이 발생한다면 -1을 출력하도록 합시다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, sum;
int dist[20][20];
bool ok[20][20];
int main() {
    FAST;
    cin >> N;
    rep(i, N) rep(j, N) {
        cin >> dist[i][j];
        sum += dist[i][j];
    }
    rep(k, N) rep(i, N) rep(j, N) {
        if ((i == k) || (k == j) || (i == j)) continue;
        if (ok[i][k] || ok[k][j] || ok[i][j]) continue;
        if (dist[i][j] == dist[i][k] + dist[k][j]) {
            ok[i][j] = true;
            sum -= dist[i][j];
        }
        else if (dist[i][j] > dist[i][k] + dist[k][j]) {
            cout << -1;
            return 0;
        }
    }
    cout << sum / 2;

    return 0;
}