https://www.acmicpc.net/problem/1738

골목길 지날 때마다 돈을 얻거나 잃는데, 수익 최대로 하면서 목적지까지 가는 최적 경로 찾는 문제이다.
벨만-포드 알고리즘의 간선완화를 사용해서 n번 돌면서 수익이 최대가 되도록 설정했고, n+1번부터 수익이 더 해지는 곳이 있다면 사이클이 있는 것으로 판단하고 -1을 출력하도록 했다.

Python

시도 1 - 실패

n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(m)]
dp = [-float("inf")] * (n + 1)
parent = [i for i in range(n + 1)]
chk = False
dp[1] = 0
for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            dp[v] = dp[u] + w
            parent[v] = u

for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            chk = True
            break

if chk:
    print(-1)
else:
    answer = [n]
    next = parent[n]
    while next != parent[next]:
        answer.append(next)
        next = parent[next]
    answer.append(1)
    print(" ".join(map(str, answer[::-1])))

5 5
1 2 -1
2 3 1
3 4 1
4 2 1
2 5 -1

이 테스트 케이스에 대해서 1에서 4로 가는 경로는 최적화가 되었지만 2, 3, 2, 3 사이클 때문에 -1을 출력하는 문제가 있었다.
그래서

if chk:
    reachable = [False] * (n + 1)
    reachable[1] = True
    for _ in range(n):
        for u, v, w in graph:
            if reachable[u]:
                reachable[v] = True
    if reachable[n]:
        visited = [False] * (n + 1)
        answer = [n]
        next = parent[n]
        while next != parent[next]:
            if visited[next]:
                print(-1)
                break
            visited[next] = True
            answer.append(next)
            next = parent[next]
        else:
            answer.append(1)
            print(" ".join(map(str, answer[::-1])))
    else:
        print(-1)

사이클이 발견됐을 때, n에서 1까지 사이클 없이 접근 가능한지 판별하는 코드를 만들었다.

시도 2 - 실패

n, m = map(int, input().split())

# 벨만 포드 알고리즘으로 조져야함.
# 벨만 포드의 간선완화 사용해서 음수 사이클 유무 찾아야한다.
# 그래서 1번에서 n번까지의 최단경로 찾아야함
# 아 아니다 돈 가장 많이 벌면서 갈 수 있는 길 찾아야함.

graph = [list(map(int, input().split())) for _ in range(m)]
dp = [-float("inf")] * (n + 1)
parent = [i for i in range(n + 1)]
chk = False
dp[1] = 0
for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            dp[v] = dp[u] + w
            parent[v] = u

for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            chk = True
            break
if chk:
    reachable = [False] * (n + 1)
    reachable[1] = True
    for _ in range(n):
        for u, v, w in graph:
            if reachable[u]:
                reachable[v] = True
    if reachable[n]:
        visited = [False] * (n + 1)
        answer = [n]
        next = parent[n]
        while next != parent[next]:
            if visited[next]:
                print(-1)
                break
            visited[next] = True
            answer.append(next)
            next = parent[next]
        else:
            answer.append(1)
            print(" ".join(map(str, answer[::-1])))
    else:
        print(-1)
else:
    answer = [n]
    next = parent[n]
    while next != parent[next]:
        answer.append(next)
        next = parent[next]
    answer.append(1)
    print(" ".join(map(str, answer[::-1])))

https://www.acmicpc.net/board/view/136016
의 샘플을 돌렸을 때 2 때문에 -1을 출력해야하지만 경로를 출력하는 문제가 있었다.

그래서 사이클 탐지 후 재검사하는 과정을
그래서

if chk:
    reachable = [False] * (n + 1)
    reachable[1] = True
    for _ in range(n):
        for u, v, w in graph:
            if reachable[u]:
                reachable[v] = True
    if reachable[n]:
        visited = [False] * (n + 1)
        answer = []
        next = n
        while next != 1:
            if visited[next]:
                print(-1)
                break
            visited[next] = True
            answer.append(next)
            next = parent[next]
        else:
            answer.append(1)
            print(" ".join(map(str, answer[::-1])))
    else:
        print(-1)

이렇게 수정했는데 그래도 실패했다.

시도 3 - 다른 코드 참고

n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(m)]

dp = [-float("inf")] * (n + 1)
dp[1] = 0
parent = [i for i in range(n + 1)]
chk = False
for i in range(1, n + 1):
    for u, v, w in graph:
        if dp[u] != -float("inf") and dp[u] + w > dp[v]:
            dp[v] = dp[u] + w
            parent[v] = u
            if i == n:
                dp[v] = float("inf")

result = []
cur_node = n
if dp[n] == float("inf"):
    print(-1)
else:
    while cur_node != 1:
        result.append(cur_node)
        cur_node = parent[cur_node]
    result.append(1)
    print(" ".join(map(str, result[::-1])))

다른 블로그에서 코드를 참고해서 가져왔다.
로직은 나랑 비슷한데 사이클 탐지부분이 달랐다. 사이클이 탐지되면 탐지된 곳에 최대값을 저장하게했다.
그러면 n번째 탐색 때, 전체 경로를 다시 검사하면서 목적지인 n이 관여하게 된다면 n에 대한 거리는 INF로 업데이트 되고 그러면 마지막에 출력부분에서 걸러지게 되는 것이다.

---

사이클 유무가 중요한 것이 아니라 목적지가 사이클에 관여했는가가 중요하기에 이전 문제와 방법을 달리 해야했다.