[1219] 오민식의 고민(변형 벨만-포드)

1219번: 오민식의 고민

 

벨만-포드 알고리즘

• 특정 출발 노드에서 다른 모든 노드까지의 최단경로 검색
• 음수 가중치 존재
• 음수 싸이클 존재 여부 판단
• 2023.03.20 - [Algorithm/Graph] - [11657번] 타임머신 (그래프, 최단거리, 벨만 포드 알고리즘)
• 수행과정
  1. 모든 에지와 관련된 정보를 가져와 다음 조건에 따라 거리 리스트의 값 업데이트
     • 출발 노드가 방문한 적이 없는 노드(출발 노드 거리 == INF) 일 때 업데이트 X
     • 출발 노드의 거리 리스트 값 + 에지 가중치 < 종료노드의 거리 리스트 값일 때, 종료 노드 거리 리스트값 업데이트
  2. 노드 개수 -1번 만큼 반복
     • 노드의 개수가 N이고 음수 사이클이 없을 때 특 정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 갯수 N-1
  3. 음수 사이클 유무를 알기 위해 모든 에지에 관해 1 수행, 한 번 이라도 값이 업데이트 되면 음수 사이클 존재로 판단

 

변형된 벨만-포드 알고리즘

• 돈을 무한히 많이 버는 케이스가 있다고 하는 것을 바탕으로 음수 사이클이 아닌 양수 사이클을 찾도록 변경
• 양수 사이클이 있어도 출발 노드에서 이 양수 사이클을 이용해 도착 도시에 가지 못할 때 예외처리
• 수행과정
  1. 모든 에지와 관련된 정보를 가져와 다음 조건에 따라 거리 리스트의 값 업데이트
     • 시작 도시가 방문한 적이 없는 도시일 때 (시작 도시==MIN) 업데이트 X
     • 시작 도시가 양수 사이클과 연결된 도시일때 (도착도시 == MAX) 도착 도시도 양수 사이클과 연결된 도시로 업데이트
     • 도착 도시값 < 시작 도시값 + 도착 도시 수입 - 에지 가중치일 때, 더 많이 벌 수 있는 새로운 경로로 도착 업데이트
  2. 노드보다 충분히 많은 값(N+100)으로 1 반복
     • 에지의 업데이트를 충분히 큰 수(도시 개수 N의 최대치=100)만큼 추가로 돌리면서 업데이트 수행
     • 에지를 충분히 탐색하면서 양수 사이클에서 도달할 수 있는 모든 노드를 양수 사이클에 연결된 노드로 업데이트하기 위해

풀이

"""
도시수 n(1~100), 시작, 종료, 교통수단 m(1~100)
교통 수단 정보 : 시작 끝 가격
각 도시에서 벌 수 있는 돈의 최댓값(0~1,000,000)

같은 도시 여러번 방문 가능
버는 돈보다 쓰는 돈이 많다면 도착 도시에 도착할때 지니고 있는 돈의 액수가 음수

* 도착도시에 도착할 때 지니고 있는 돈의 최대 액수
도착 불가 'gg'
무한 'Gee'
"""

import sys
input=sys.stdin.readline

# 도시수 n(1~100), 시작, 종료, 교통수단 m(1~100)
n,s,e,m=map(int, input().split())
graph = [] # 교통 수단 정보, 에지 리스트
d = [-sys.maxsize]*n # 최단 경로 리스트

# 교통 수단 정보, 에지 리스트
for _ in range(m):
    u, v, w = map(int, input().split())
    graph.append((u, v, w))

# 각 도시에서 벌 수 있는 돈의 최댓값
mList=list(map(int,input().split()))

d[s] = mList[s]
# 변형 벨만-포드
for i in range(n+101):
    for start, end, price in graph:
        if d[start]==-sys.maxsize: # 출발노드 미방문 노드
            continue
        elif d[start]==sys.maxsize: # 출발노드가 양수 사이클에 연결된 노드
            d[end]=sys.maxsize
        elif d[end] < d[start]+mList[end]-price: # 종료노드값 < 출발노드값+도착도시수입+에지가중치
            d[end]=d[start]+mList[end]-price

            # 에지 사용 횟수가 n-1을 넘어선 이후 갱신되면 양수 사이클에 연결되어 있다는 의미
            # 종료노드를 양수 사이클 연결 노드로 업데이트
            if i >= n-1:
                d[end]=sys.maxsize

if d[e] == -sys.maxsize: # 도착 불가능
    print("gg")
elif d[e]==sys.maxsize: # 양수싸이클, 무한대
    print("Gee")
else:
    print(d[e])