[백준]1507 궁금한민호

1.풀이

모든쌍의 최단거리가 나타나 있고, 간선의 개수를 최소로 해야 한다.

따라서 모든 도시간의 최단거리를 가진 간선이 존재한다고 생각을 하고, L[i][j]=L[i][k]+L[k][j]를 만족하는 간선 i - j 는 k를 거쳐가면 되기 때문에 없애주는 방식으로 진행.

불가능한 경우는 도시i와 도시j의 최단거리 L[i][j] 보다 k를 거쳐가는 L[i][k]+L[k][j] 가 더 작은 경우가 존재하는 경우

​

2. 소스코드

import sys

N=int(input())
L=[]
for i in range(N):
    L.append(list(map(int,input().split())))
edge=[[1 for j in range(N)] for i in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i==j:
                edge[i][j]=-1
            elif i==k or k==j:
                continue
            elif L[i][j]==L[i][k]+L[k][j]:
                edge[i][j]=-1
            elif L[i][j]>L[i][k]+L[k][j]:
                print(-1)
                sys.exit()
ans=0
for i in range(N):
    for j in range(i,N):
        if edge[i][j]==1:
            ans+=L[i][j]

print(ans)