백준 1507 궁금한 민호

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

1507번: 궁금한 민호

이 문제는 플로이드 와샬을 역으로 활용하면 된다. 조금 생각해보면 직관적으로 그 아이디어가 떠오를 것이다. 그리고 그게 맞다!

플로이드 와샬 알고리즘을 이용해 최단경로를 구할 때, 최소값으로 계속 갱신해준다. 이번에는 그러한 경우가 발생할 때마다 해당 경로를 지워주면 된다. 각 정점들을 연결하는 도로정보가 주어지는데, 이들을 모두 더할 경우, 모든 도로의 가중치 합의 2배가 된다. 그러므로 중복 경로 삭제 후에 절반으로 나누어서 출력해줘야 함에 주의하자.

 

그리고 '불가능한 경우'라는게 있다. 이것은 당연히 플로이드 와샬로 연산을 하다가 dp[i][k]+d[k][j] < dp[i][j] 인 경우에 해당하게 된다.

 

<주요 내용>

플로이드 와샬

 

<코드>

C++

#include <iostream>
#define endl '\n'
using namespace std;

const int sz=20+1;
int r[sz][sz],rn[sz][sz],n,t;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>n;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cin>>r[i][j];
            rn[i][j]=r[i][j];
            t+=r[i][j];
        }
    }
    for(int k=0;k<n;++k){
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(i==k||k==j||j==i)continue;
                if(r[i][j]==r[i][k]+r[k][j]){
                    if(rn[i][j])t-=r[i][j];
                    rn[i][j]=0;
                }else if(r[i][j]>r[i][k]+r[k][j]){
                    cout<<-1;
                    return 0;
                }
            }
        }
    }
    cout<<t/2;
    return 0;
}

 

파이썬

import sys
import copy
si = sys.stdin.readline


def main():
    n = int(si())
    routes = []
    for _ in range(n):
        routes.append([int(e) for e in si().split()])

    nroutes = copy.deepcopy(routes)
    for k in range(n):
        for i in range(n):
            if k == i:
                continue
            for j in range(n):
                if i == j or j == k:
                    continue
                if routes[i][k]+routes[k][j] == routes[i][j]:
                    nroutes[i][j] = 0
                elif routes[i][j] > routes[i][k]+routes[k][j]:
                    print(-1)
                    return

    t = 0
    for i in range(n):
        for j in range(i, n):
            t += nroutes[i][j]
    print(t)


if __name__ == '__main__':
    main()