골목길

• 오민식의 고민와 비슷하다. 최대한 많이 버는 경로를 구하는 문제를, 각 가중치들의 부호를 반대로 하면, 단일 출발지 최단 경로 (Single Source Shortest Path) 문제로 풀 수 있게 된다. 이때는 단일 출발지 최단 경로 (Single Source Shortest Path)에서 설명한 대로 SPFA를 쓰면 O(VE)에 풀 수 있다.
• 오민식의 고민와 다른 차이점은, 경로 자체를 출력하는 문제라는 점. 경로 트래킹을 포함시키면 된다

"""Solution code for "BOJ 1738. 골목길".

- Problem link: https://www.acmicpc.net/problem/1738
- Solution link: http://www.teferi.net/ps/problems/boj/1738

Tags: [SPFA]
"""

import sys
from teflib import tgraph

INF = float('inf')


def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(n)]
    for _ in range(m):
        u, v, w = [int(x) for x in sys.stdin.readline().split()]
        try:
            cost = min(wgraph[u - 1][v - 1], -w)
        except KeyError:
            cost = -w
        wgraph[u - 1][v - 1] = cost

    prev = [None] * n
    distance = tgraph.spfa(wgraph, 0, prev)[n - 1]
    if distance == -INF:
        print('-1')
    else:
        cur = n - 1
        answer = [cur + 1]
        while (cur := prev[cur]) is not None:
            answer.append(cur + 1)
        print(*reversed(answer))


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.spfa