백준 11657 타임머신

INF = int(1e9)
def solution() :
    for i in range(node):
        for s,e,v in edgeArr:
            if dist[s] != INF and dist[e] > dist[s] + v :
                dist[e] = dist[s] + v
                if i == node-1:
                    return True
    return False

node, edge = map(int, input().split())
edgeArr = []
dist = [INF] * (node + 1)
dist[1] = 0

for i in range(edge) :
    edgeArr.append(list(map(int,input().split())))

if solution() :
    print(-1)
else :
    for i in range(2, node+1):
        if dist[i] == INF:
            print(-1)
        else :
            print(dist[i])

음수 사이클을 찾아야 하기에 벨만 포드로 푸는 문제이다.

아무생각없이 워셜 플로이드로 해봤다가 바로 타임아웃ㅎ