백준 11657. 타임머신

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

import sys
input = sys.stdin.readline

n, m = map(int, input().split())  # 도시의 개수와 버스 노선 개수
edges = []  # 간선 정보를 담을 리스트
dist = [float('inf')] * (n + 1)

for _ in range(m):
    start, end, cost = map(int, input().split())
    edges.append((start, end, cost))

def bf(start):
    dist[start] = 0  # 시작 노드의 거리 초기화
    for i in range(n):
        for s, e, w in edges:
            if dist[s] != float('inf') and dist[s] + w < dist[e]:
                dist[e] = dist[s] + w
                if i == n-1: # n-1번째에도 갱신이 일어나는 경우 -> 무한음수루프 존재
                    return True
    return False

if bf(1): # 무한음수루프 유무 확인
    print(-1)
else:
    for i in range(2, n + 1):
        if dist[i] == float('inf'):  # 도달할 수 없는 경우
            print(-1)
        else:
            print(dist[i])

다른 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())  # 도시의 개수와 버스 노선 개수
edges = [[] for _ in range(n + 1)]  # 인접 리스트 초기화
dist = [float('inf')] * (n + 1)

for _ in range(m):
    start, end, cost = map(int, input().split())
    edges[start].append((end, cost))  # 시작 노드 기준으로 간선 저장

def bf(start):
    dist[start] = 0  # 시작 노드의 거리 초기화
    for i in range(n):
        for u in range(1, n + 1):  # 모든 노드에 대해 확인
            if dist[u] == float('inf'):  # 시작 노드에 도달하지 못한 경우는 무시(시작 노드로부터 연결되지 않았거나, 아직 접근할 수 없는 상태)
                continue
            for v, w in edges[u]:  # 연결된 모든 간선 확인
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    if i == n-1:  # n-1번째에도 갱신이 일어나는 경우
                        return True  # 무한 음수 루프 존재
    return False

if bf(1):  # 무한 음수 루프 유무 확인
    print(-1)
else:
    for i in range(2, n + 1):
        if dist[i] == float('inf'):  # 도달할 수 없는 경우
            print(-1)
        else:
            print(dist[i])