• 음수 가중치가 있는 그래프에서 시작점을 포함하는 음수 사이클이 존재하는지를 찾는 문제.
• 벨만포드 알고리즘이나 SPFA를 사용해서 O(VE)에 풀수 있다. 단일 출발지 최단 경로 (Single Source Shortest Path) 참조

"""Solution code for "BOJ 10360. The Mountain of Gold?".

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

Tags: [SPFA]
"""

import sys
from teflib import tgraph

INF = float('inf')
START = 0


def main():
    T = int(sys.stdin.readline())
    for case_no in range(1, T + 1):
        # pylint: disable=unused-variable
        N, M = [int(x) for x in sys.stdin.readline().split()]  
        wgraph = [{} for _ in range(N)]
        for _ in range(N):
            A, B, C = [int(x) for x in sys.stdin.readline().split()]
            try:
                wgraph[A][B] = min(wgraph[A][B], C)
            except KeyError:
                wgraph[A][B] = C

        dists = tgraph.spfa(wgraph, START)
        answer = 'possible' if dists[START] == -INF else 'not possible'
        print(f'Case #{case_no}: {answer}')


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.spfa