웜홀 ( 1865번 )

1865번: 웜홀

 

나의 풀이

import sys

def _info_road(m, w):
    graph = []
    for _ in range(m):
        s, e, t = map(int, sys.stdin.readline().rstrip().split())
        graph.append((s, e, t))
        graph.append((e, s, t))
    for _ in range(w):
        s, e, t = map(int, sys.stdin.readline().rstrip().split())
        graph.append((s, e, -t))
    return graph

def _ball(n, start, graph):
    visit = [int(1e9)] * n
    visit[start - 1] = 0
    for i in range(n):
        for s, e, t in graph:
            if (visit[e - 1] > (visit[s - 1] + t)):
                if (i == (n - 1)): # 음의 사이클 존재
                    return "YES"
                visit[e - 1] = (visit[s - 1] + t)
    return "NO"
        
case = int(sys.stdin.readline().rstrip())
for _ in range(case):
    n, m, w = map(int, sys.stdin.readline().rstrip().split())
    graph = _info_road(m, w)
    print(_ball(n, 1, graph))

 

시간 복잡도

for i in range(n) : n번 순회 ( 선형 시간 복잡도 )
    for s, e, t in graph : 경로 순회 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )