1. 문제

---

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

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

2. 아이디어

---

• 벨만-포드 알고리즘

  이전 최단거리보다 더 작으면 갱신하고 다시 돌 때(N번 돌았을 때) 한 번이라도 갱신된다면 음의 사이클이 있다는 것.

출처 : https://www.youtube.com/watch?v=Ppimbaxm8d8

3. 코드

---

clone

N,M=map(int,sys.stdin.readline().split())#도시개수 버스 노선개수
G=[]
for _ in range(M):
    G.append(list(map(int,sys.stdin.readline().split())))#출발 도착 거리

INF=sys.maxsize
result=[INF for _ in range(N+1)]
result[1]=0#자신으로 가는길만 초기화
check=0#음의 싸이클 체크

for i in range(N):#노드 갯수만큼 반복
    for j in range(M):#모든간선을 확인하며 거리갱신
        s=G[j][0]#출발
        e=G[j][1]#도착
        d=G[j][2]#거리
        if result[s]!=INF and result[e]>result[s]+d:#이전거리보다 작아서 갱신해야 한다면
            result[e]=result[s]+d
            if i==N-1:#N번돌았을때 갱신된다면
                check=1#음의 사이클이 있다

if check:
    print(-1)
else:
    for i in range(2,N+1):
        if result[i]==INF:
            print(-1)
        else:
            print(result[i])

출처 : https://developmentdiary.tistory.com/394