목차

The Mountain of Gold?

ps
링크acmicpc.net/…
출처BOJ
문제 번호10360
문제명The Mountain of Gold?
레벨골드 2
분류

SPFA

시간복잡도O(T*V*E)
인풋사이즈T<=20, V<=1000, E<=2000
사용한 언어Python
제출기록35072KB / 4648ms
최고기록4648ms
해결날짜2021/09/23

풀이

코드

"""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()

,