BOJ 11657(타임머신)풀이

solved.ac 티어 : 골드 4

 

www.acmicpc.net/problem/11657

11657번: 타임머신

문제보면 바로 다익스트라인걸 알수있다. 다익스트라를 구현해주고 출력하면 된다.

import sys,math
input=sys.stdin.readline
n,m=map(int,input().split())
adj=[[]for i in range(n)]
inf=math.inf
for i in range(m):a,b,c=map(int,input().split());adj[a-1].append([b-1,c])
ch=0;dist=[0]+[inf for i in range(n-1)]
for i in range(n):
    for g in range(n):
        for q in adj[g]:
            nex=q[0];d=q[1]
            #print(dist[g]+d)
            if dist[g]!=inf and dist[nex]>dist[g]+d:
                dist[nex]=dist[g]+d
                if i==n-1:ch=1
if ch:print(-1)
else:
    for i in range(1,n):
        if dist[i]!=inf:print(dist[i])
        else:print(-1)