1507번: 궁금한 민호

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


$O(n^3)$

두 지점 i,j에 대해 k를 거쳐가서 가능한 최소 거리가 원래의 i-j 최소거리와 같다면 원래의 i-j 최소경로를 삭제해도 된다.(그보다 작다면 모순이다.)
이것을 삭제해도 i-k-j 경로가 남아 있기 때문에 아무런 지장이 없다. 최대한 삭제한 다음 모든 도로 시간합을 출력하자.

#include<stdio.h>
#define min(x,y) x<y?x:y
int n, s, c[20][20];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &c[i][j]), s += c[i][j];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int mini = 0x7fffffff;
            for (int k = 0; k < n; k++)
                if (i != k&&j != k) mini = min(mini, c[i][k] + c[j][k]);
            if (mini < c[i][j]) {
                puts("-1");
                return 0;
            }
            else if (mini == c[i][j]) s -= c[i][j];
        }
    }
    printf("%d", s / 2);
    return 0;
}