[BOJ] 1219. 오민식의 고민

 

www.acmicpc.net/problem/1219

1219번: 오민식의 고민

문제: 민식이가 S 도시부터 E 도시까지 가서 벌 수 있는 돈의 최댓값을 구하여라.

 

민식이의 고민보다 더 고통스러운 고민이었던 것 같습니다..ㅠ

문제를 풀면서 16~17퍼에서 자꾸 WA가 떠서 정말 힘들었던 문제에요.

 

최종적으로 찾아낸 반례는

4 0 3 4
0 1 0
0 3 5
1 2 0
2 1 0
0 5 5 10

답: 5

입니다.

타임머신이나 웜홀에서 썻던 코드를 들고와서 재사용했던게 문제가 되네요.

 

밑을 보시면 벨만포드(BF)쪽 코드는 비슷합니다.

다만 안에 check가 추가되어 있다는 점입니다.

check는 dfs를 사용했습니다.

q라고 되어있어서 bfs로 착각할 수도 있지만 그건 페이크^^

 

어쨋든 사이클을 돈다면 그 사이클에서 E 도시로 갈 수 있어야 합니다.

이게 바로 핵심이죠!

위에 있는 반례를 손으로 그리시다 보면 바로 "아!!" 하실 겁니다 ㅎㅎ

다들 화이팅~~!

 

코드:

def check(E):
    visit = [0] * N
    q = [E]
    while q:
        a = q.pop()
        if a == End:
            return True
        visit[a] = 1
        for b, c in network[a]:
            if visit[b] == 0:
                q.append(b)
    return False


def BF():
    for i in range(N+1):
        if sections[End] == -float('inf') and i == N:
            print('gg')
            return
        for j in range(N):
            if sections[j] == -float('inf'):
                continue
            for E, T in network[j]:
                if sections[j] + T > sections[E]:
                    sections[E] = sections[j] + T
                    if i == N:
                        if check(E):
                            print('Gee')
                            return False
    return True


N, Start, End, M = map(int, input().split())
sections = [-float('inf')] * N
network = [[] for i in range(N)]
for i in range(M):
    S, E, T = map(int, input().split())
    network[S].append([E, T])
salary = list(map(int, input().split()))
sections[Start] = salary[Start]
for i in range(len(salary)):
    for j in range(len(network[i])):
        for k in range(len(salary)):
            if network[i][j][0] == k:
                network[i][j][1] = salary[k] - network[i][j][1]

if BF():
    print(sections[End])