백준_1507_궁금한 민호

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

1507번: 궁금한 민호

해결 방법

> 문제의 입력으로 각 도시마다의 '최소 걸리는 시간'이 2차원 배열로 주어진다.

> 2차원 배열로 주어지며, (i,i)의 값이 0이며 대각석을 기준으로 대칭인 것으로 보아 플로이드-워셜의 output 형태로 판단하였다.

> 플로이드 - 워셜을 역으로 돌리면서 불필요한 간선을 지운다.

 

코드

import sys, copy

 

input = sys.stdin.readline

 

num_city = int(input())

time_city = list()

 

for i in range(num_city):

    time_city.append(list(map(int, input().split())))

 

copy_time_city = copy.deepcopy(time_city)

 

def check(num_city, time_city, copy_time_city):

    for k in range(num_city):

        for i in range(num_city):

            for j in range(num_city):

                #대각선 처리

                if k == i or i == j or j == k:

                    continue

                #최단 경로가 주어져 있는데 그것보다 클 수는 없다

                if time_city[i][j] > time_city[i][k] + time_city[k][j]:

                    return print(-1)

                #도로 갯수 최소화

                if time_city[i][j] == time_city[i][k] + time_city[k][j]:

                    copy_time_city[i][j] = 0

    count = 0

    for i in copy_time_city:

        count += sum(i)

 

    return print(count//2)    

 

check(num_city, time_city, copy_time_city)