060 오민식의 고민

첫번째 코드

 

벨만-포드 알고리즘을 반대로 생각하는 문제이다.

벨만-포드 자체에 익숙하지 않지만 반대로 하라고 하니 더 정신이 없다...

 

코드는 책을 참고했다!

그래도 전반적인 개념에 대한 코드와 적응하고 있다!

꼭 다시 풀어봐야하는 문제이다!!

 

import sys
input = sys.stdin.readline

n, scity, ecity, m = map(int, input().split())
A = []
distance = [-sys.maxsize] * n

for i in range(m):
    s, e, p = map(int, input().split())
    A.append((s, e, p))

money = list(map(int, input().split()))

distance[scity] = money[scity]

for i in range(n + 101):
    for s, e, p in A:
        if distance[s] == -sys.maxsize:
            continue
        elif distance[s] == sys.maxsize:
            distance[e] = sys.maxsize
        elif distance[e] < distance[s] + money[e] - p:
            distance[e] = distance[s] + money[e] - p
            if i >= n-1:
                distance[e] = sys.maxsize

if distance[ecity] == -sys.maxsize:
    print('gg')
elif distance[ecity] == sys.maxsize:
    print("Gee")
else:
    print(distance[ecity])

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Platinum/1219.%E2%80%85%EC%98%A4%EB%AF%BC%EC%8B%9D%EC%9D%98%E2%80%85%EA%B3%A0%EB%AF%BC

programmers/백준/Platinum/1219. 오민식의 고민 at main · ornni/programmers