문제 바로가기
문제:
오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다. 오민식은 고민에 빠졌다. 어떻게 하면 최대 이윤을 낼 수 있을까? 이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다. 오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다. 오민식은 도착 도시에 도착할 때, 가지고 있는 돈의 액수를 최대로 하려고 한다. 이 최댓값을 구하는 프로그램을 작성하시오. 오민식이 버는 돈보다 쓰는 돈이 많다면, 도착 도시에 도착할 때 가지고 있는 돈의 액수가 음수가 될 수도 있다. 또, 같은 도시를 여러 번 방문할 수 있으며, 그 도시를 방문할 때마다 돈을 벌게 된다. 모든 교통 수단은 입력으로 주어진 방향으로만 이용할 수 있으며, 여러 번 이용할 수도 있다.
입력:
첫째 줄에 도시의 수 N과 시작 도시, 도착 도시 그리고 교통 수단의 개수 M이 주어진다. 둘째 줄부터 M개의 줄에는 교통 수단의 정보가 주어진다. 교통 수단의 정보는 “시작 끝 가격”과 같은 형식이다. 마지막 줄에는 오민식이 각 도시에서 벌 수 있는 돈의 최댓값이 0번 도시부터 차례대로 주어진다. N과 M은 50보다 작거나 같고, 돈의 최댓값과 교통 수단의 가격은 1,000,000보다 작거나 같은 음이 아닌 정수이다.
출력:
첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착했을 때 돈을 무한히 많이 가지고 있을 수 있다면 "Gee"를 출력한다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, s, e, m = map(int, sys.stdin.readline().rstrip().split())
graph = [list(map(int, sys.stdin.readline().split(" "))) for _ in range(m)]
lst = list(map(int, sys.stdin.readline().rstrip().split()))
INF = -1e9
dist = [INF] * n
def Bellman_ford(s):
dist[s] = lst[s]
for i in range(n):
for j in range(m):
u, v, e = graph[j]
if dist[u] != INF and dist[u] - e + lst[v] > dist[v]:
dist[v] = dist[u] - e + lst[v]
# 음의 사이클 찾기
negative_cycle = [False] * n
for u, v, e in graph:
if dist[u] != INF and dist[u] - e + lst[v] > dist[v]:
negative_cycle[v] = True
# 음의 사이클과 연결된 것들 다 음의 사이클로 넣음
for _ in range(n):
for u, v, e in graph:
if negative_cycle[u]:
negative_cycle[v] = True
return negative_cycle
res = Bellman_ford(s)
# 결과 출력
if dist[e] == INF:
print("gg")
elif res[e]:
print("Gee")
else:
print(dist[e])
이 문제는 벨만 포드 문제이다.
일단 한 바퀴 돌린 것을 dist에 저장한 후에 싸이클이 있는 좌표들을 찾는다.
음의 사이클이 있는 곳의 좌표를 negative_cycle 이라고 선언하고 만약 싸이클 안에 들게 된다면 연결된 좌표들도 음의 사이클에
포함된다고 바꿔준다.
그리고 dist[타겟노드] 에 따라서 출력해준다.
댓글