[BOJ] 1507 - 궁금한 민호

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

BOJ - 궁금한 민호

문제 유형: 그래프, 최단경로, 플로이드-워셜

문제 난이도: Gold II

시간 제한: 2초

메모리 제한: 128MB

 

문제

강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.

도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.

강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.

예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다. 예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도, 강호가 구한 모든 쌍의 최솟값을 구할 수 있다. 이 경우 도로의 개수는 6개이고, 모든 도로의 시간의 합은 55이다.

모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값일 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 0이 주어지고, 그 외의 경우에 필요한 시간은 2500보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다. 불가능한 경우에는 -1을 출력한다.

 

풀이

입력은 플로이드-워셜의 결과이다.

mst-like로 그래프를 다시 만들어서, 플로이드 워셜 알고리즘을 돌린 후, 입력값과 비교하여 맞으면 총 간선들의 가중치의 합, 아니라면 -1을 출력해주면 된다.

 

플로이드-워셜의 결과들을 최소 힙에 넣고, 뽑아서 후보 <w, u, v>가 적합한지 알아낸다.

만약 u -> v의 최단거리가 w보다 크다면, w간선을 추가하여 직접 이으면 된다. 인접행렬에서 연결하고, 정답 출력을 위해 가중치를 따로 누적해놓는다.

 

복원된 그래프의 플로이드-워셜 결과와 입력값이 같으면 가중치들의 합을 출력하고, 실패 시 -1을 출력한다.

 

 

코드

C++

#include <bits/stdc++.h>
#define tiii tuple<int, int, int>
#define pii pair<int, int>

using namespace std;

int n;

int getDist(int src, int dst, vector<vector<int>>& adj) {
    vector<int> dist(n + 1, 1e9);
    dist[src] = 0;
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();
        int curDist = curr.first;
        int curNode = curr.second;

        if (dist[curNode] < curDist) continue;
        for (int i = 1; i <= n; i++) {
            if (dist[i] > curDist + adj[curNode][i]) {
                dist[i] = curDist + adj[curNode][i];
                pq.push({dist[i], i});
            }
        }
    }

    return dist[dst];
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    vector<vector<int>> adj(n + 1, vector<int>(n + 1, 1e9));
    vector<vector<int>> floyd_result(n + 1, vector<int>(n + 1));
    priority_queue<tiii, vector<tiii>, greater<>> pq;

    for (int i = 1; i <= n; i++) {
        adj[i][i] = 0;
        for (int j = 1; j <= n; j++) {
            cin >> floyd_result[i][j];
        }
    }

    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            pq.push(make_tuple(floyd_result[i][j], i, j));
        }
    }

    int ans = 0;
    while (!pq.empty()) {
        int w, u, v;
        tie(w, u, v) = pq.top();
        pq.pop();

        if (getDist(u, v, adj) > w) {
            ans += w;
            adj[u][v] = w;
            adj[v][u] = w;
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (adj[i][j] != floyd_result[i][j]) {
                cout << "-1\n";
                return 0;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}