[백준 1865번] 웜홀 (Python3)

import sys
input = sys.stdin.readline
INF = 2000000000

def BF(start):
  bf = [INF]*(N+1)
  bf[start] = 0
  for i in range(N):
    for x1,x2,t in graph:
      if bf[x2] > bf[x1]+t:
        bf[x2] = bf[x1]+t
        if i == N-1:
          return True
  return False
        
      
T = int(input())

for test in range(T):
  N,M,W = map(int,input().split())
  graph = []
  for i in range(M):
    x1,x2,t = map(int,input().split())
    graph.append((x1,x2,t))
    graph.append((x2,x1,t))
  for i in range(W):
    x1,x2,t = map(int,input().split())
    graph.append((x1,x2,-t))

  result = "NO"
  if BF(1):
    result = "YES"
    
  print(result)

 

이 문제는 풀긴 풀었는데 이걸 풀었다고 봐야 할지 모르겠다.

 

처음에는 다 익스트라로 구현해보려 했는데, 음수일 때는 적용할 수 없다는걸 알게 되었다. 그래서 플로이드 알고리즘을 이용했더니 시간초과가 나버렸다.

 

결국 벨만 포드 알고리즘을 검색해서 사실상 베끼다싶이 풀었는데, 문제는 그래도 안풀렸다. 한참을 쥐어짜내다 알아낸건 for i in range(M) 에서 그래프를 양방향이 아니라 단방향으로 데이터를 삽입했다는 것이었다...

 

그래도 시간초과가 발생했는데, 이것도 그냥 검색해서 알아낼 수밖에 없었고 결론은 벨만포드 알고리즘을 N번 하는게 아니고 노드를 아무거나 잡고 하면 되는거였다.

 

이런 알고리즘이 정해진 문제는 정말 풀기도 싫고 재미도 없는것 같다...

 

 

 

오늘의 교훈) 음... 이론 공부를 해보자?