11404 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

 

 

아주아주아주 기초적인 플로이드 문제이다.

 

문제를 읽는순간 플로이드와샬 코드를 떠올릴 수 있어야 한다.

 

하지만 마자막에 "갈수없는 경로에는 0을 출력한다"를 보지 않았다면 98%에서 틀렸습니다를 볼 것이다.

 

이번 하반기 11번가 코딩테스트도 매우쉬웠으나 아주 사소한 예외처리 히든 테케때문에 많이들 털렸다고 한다 주의하자!

 

 

import sys
input = sys.stdin.readline

n = int(input().rstrip())
m = int(input().rstrip())
INF = int(1e9)
graph = [ [INF]*(n+1) for _ in range(n+1) ]
for _ in range(m):
    start, end, weight = map(int, input().rstrip().split(" "))
    graph[start][end] = min(weight,graph[start][end])

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            graph[i][j] = min( graph[i][j], graph[i][k]+graph[k][j] )

for i in range(n+1):
    graph[i][i] = 0
    for j in range(n+1):
        if(graph[i][j] == INF):
            graph[i][j] = 0

for i in graph[1:]:
    print(" ".join(map(str,i[1:])))