[BOJ] 궁금한 민호

문제

강호는 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개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 필요한 시간은 0이다.

출력

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

 

1507

맞았습니다!!

1984

0

C++14 / 수정

1152

41초 전

 

1) 플로이드 와샬 알고리즘과 그래프 이론으로 풀이 

 

2) 1->2 로 가는 도로가 있고 2->3으로 가는 도로가 있을 때 이 두 도로의 비용 합이 1->3과

같다면 1->3은 최소 도로 수에 포함되지 않는 도로이고(제외되어야 하는 도로)

작다면 잘못된 경우이다. 

 

3) 잘못된 경우일 때는 -1을 출력하고 종료 

 

4) 같다면 1->3을 없애준다. cost[1][3] = 0

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, map[21][21]= {{0}}, cost[21][21] = {{0}};
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
            cost[i][j] = map[i][j];
        }
    }
 
    bool flag = true;
    for (int a = 1; a <= n; a++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j<= n; j++) {
                if (a == i || a == j) continue;
 
                if (map[i][j] > map[i][a] + map[a][j]) {
                    cout << -1 << '\n';
                    return 0;
                }
                if (map[i][j] == map[i][a] + map[a][j]) {
                    cost[i][j] = 0;
                }
            }
        }
    }
 
    //1->2, 2->3 이 주어졌을 때 1->3 이 1->2 + 2->3과 비용이 같다면 1->3은 없어도 되는 도로이다. 
 
    int res = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            if(cost[i][j] >= 1) res += cost[i][j];
 
        }
    }
    cout << res << '\n';
    return 0;
}