[백준 / Python] 11404 - 플로이드

결과

• 메모리: 126224KB
• 시간: 348ms

www.acmicpc.net/source/24194515

해결방식

• 전형적인 플로이드 문제.
• maxsize를 import 하지 않고 100000정도로 설정하면 너무 작아서 "틀렸습니다"가 뜬다. 주의하기.

제출코드

# 제출  
from sys import maxsize # 큰 값  
max = maxsize  

n = int(input())  
m = int(input())  
route = \[\[max\] \* n for \_ in range(n)\]  

# 1. 도시1에서 도시1의 비용은 0이니까  
for i in range(n):  
    route\[i\]\[i\] = 0  

# 2. 각 도시 간의 비용 연결  
for \_ in range(m):  
    a, b, c = map(int, input().split())  
    # 이미 입력된 적이 있고, origin 보다 c가 더 작으면  
    if route\[a - 1\]\[b - 1\] < max:  
        if c < route\[a - 1\]\[b - 1\]:  
            route\[a - 1\]\[b - 1\] = c  
    else:  
        route\[a - 1\]\[b - 1\] = c  


# 3. printArr 함수  
def printArr(arr):  
    for i in arr:  
        for j in i:  
            print(j, end = " ")  
        print()  

# 4. floyd 함수  
def floyd():  
    for k in range(n):  
        for i in range(n):  
            for j in range(n):  
                if route\[i\]\[k\] + route\[k\]\[j\] < route\[i\]\[j\]:  
                    route\[i\]\[j\] = route\[i\]\[k\] + route\[k\]\[j\]  

floyd()  

# 5. 여전히 max인 곳은 0으로 바꾸기  
for i in range(n):  
    for j in range(n):  
        if route\[i\]\[j\] == max:  
            route\[i\]\[j\] = 0  

printArr(route)