[Python/파이썬] 백준 1865번: 웜홀

문제

풀이

벨만 포드 알고리즘을 사용해서 풀면 된다.

단, 일반적인 벨만 포드 알고리즘이 아닌 "음의 간선 사이클"이 존재하는지 여부만 구하면 된다.

또한 "도로"는 양방향이고 "웜홀"은 단방향임을 주의해서 입력받아야 한다.

 

https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13 

코드

from sys import stdin
input = stdin.readline

def bf():
      for i in range(n):
            for j in range(len(edges)):
                  cur, next, cost = edges[j]
                  if dist[next] > dist[cur] + cost:
                        dist[next] = dist[cur] + cost
                        if i == n - 1:
                              return True
      return False
                        
TC = int(input())

for _ in range(TC):
      n, m, w = map(int, input().split())
      edges = []
      dist = [1e9] * (n + 1)
      for i in range(m + w):
            s, e, t = map(int, input().split())
            if i >= m:
                  t = -t
            else:
                  edges.append((e, s, t))
            edges.append((s, e, t))
      if bf():
            print("YES")
      else:
            print("NO")

마무리

다익스트라 알고리즘과 유사한 점이 많아 쉽게 풀었다.