#59. 타임머신으로 빨리 가기(11657)

1. 문제 분석하기

• A = S(출발), B = E(도착), C = W(가중치)

• 음수 가중치 에지가 존재할 수 있다.

  ⇒ 벨만 포드 알고리즘

• ‘시간을 무한히 오래 전으로 되돌릴 수 있다.’ → 음수 사이클을 확인해 보아야 한다.

2. 손으로 풀어보기

1) 리스트 초기화

• 에지 리스트에 에지 데이터를 저장한 후 거리 리스트를 다음과 같이 초기화
• 최초 시작점에 해당하는 거리 리스트 값들을 0으로 초기화

2) 벨만-포드 알고리즘 수행

3) 음수 사이클 체크

• 1 → 2: 값이 갱신됨

  • distance[2] = 2 > distance[1] + 4 = 0

    ⇒ 값이 갱신됨!

print(-1)

3. Pseudo-code

**## 입력**
N(도시 = 노드), M(노선 = 에지)
edges(에지 리스트)
distance(거리 리스트)

for i in range(M):
	에지 리스트에 정보 저장

**## 처리**
1. 리스트 초기화(출발 노드를 0으로)
2. 정답 리스트 업데이트
    repeat (N-1)
	    repeat (M)
       현재 에지 정보 가져오기
       if 출발 노드 != 무한대 and E > (S + W):
         distance[E] = distance[S] + W
3. 음수 사이클 확인
    repeat (M)
    현재 에지 정보 가져오기
    if 출발 노드 != 무한대 and E > (S + W):
      음수 사이클 존재
      
**## 출력**
음수 사이클 존재 x -> print(distance)
음수 사이클 존재 -> print(-1)