https://www.acmicpc.net/problem/1865

시간여행 하는데 웜홀타고가면 시간이 역행한다. 그래서 어떤 점에서 다른 점 타고타고 다시 시작점으로 돌아왔을 때 시간이 역행된 경우가 있는지 찾는 문제이다.

Python

1차 실패

from heapq import heappush, heappop

def find(x, parent):
  if x != parent[x]:
    parent[x] = find(parent[x], parent)
  return parent[x]

def union(a, b, parent):
  pa = find(a, parent)
  pb = find(b, parent)
  
  if(pa == pb):
    return False
  parent[pb] = pa
  return True

for _ in range(int(input())):
  n, m, w = map(int, input().split())
  heap = []
  for _ in range(m):
    s, e, t = map(int, input().split())
    heappush(heap, (t, s, e))
  
  for _ in range(w):
    s, e, t = map(int, input().split())
    heappush(heap, (-t, s, e))
  
  parent = [i for i in range(n+1)]
  count = 0
  unused = []
  while heap:
    t, s, e = heappop(heap)
    if union(s, e, parent):
      count += t
    else:
      unused.append(t)
  chk = False
  for u in unused:
    if count + u < 0:
      chk = True
      break
  
  if chk:
    print("YES")
  else:
    print("NO")

벨만 포드 알고리즘을 활용해서 최소신장트리의 거리를 구했다. 그리고 사용안 된 간선은 따로 저장했다. 얘네가 쓰인다는 것은 사이클이 생긴다는 것이고 그 간선의 값과 더해서 음수인 경우가 존재할 경우 YES를 출력하도록 했다.

그리고 32%에서 실패했다. 질문게시판을 확인하니까 S==E인 경우가 있다고 한다. 그리고 생각해보니까 전체 트리의 값에 사이클 간선의 값을 더하는 게 틀린 것 같기도 하다. a에서 a로 가는 사이클에 포함 안 된 간선의 값도 더해지게 돼서 답이 제대로 안 나온 것 같기도 하다.

시도 2

for _ in range(int(input())):
  n, m, w = map(int, input().split())
  
  edges = []
  for _ in range(m):
    s, e, c = map(int, input().split())
    edges.append((c, s, e))
    edges.append((c, e, s))
    
  for _ in range(w):
    s, e, c = map(int, input().split())
    edges.append((-c, s, e))
    
  dp = [0] * (n+1)
  
  chk = False
  for i in range(1, n+1):
    for c, s, e in edges:
      if dp[s] + c >= dp[e]: continue
      dp[e] = dp[s] + c
      if i == n:
        chk = True
        
  print("YES" if chk else "NO")

MST와 BFS로 모든 점에 대해서 edge를 탐색하려고 했는데 답이 안 나와서 다른 사람의 풀이를 참고했다.
벨만 포드 알고리즘을 몇 번 사용했지만 이 경우는 처음 보는 사용 방식이었다.
간선완화라고 하는 것인데 음의 값을 가진 사이클을 찾는데 사용하는 방식이라고 한다.
n개의 정점이 있을 때 최대 사용되는 간선의 개수는 n-1개이고, n-1회까지는 사이클이 없는 최소 거리가 dp에 기록되게 된다.
그리고 마지막 n번째 반복에서 만약 dp값이 업데이트된다면 이것은 음의 값을 가지는 사이클이 존재한다는 의미가 되고, 이 사이클을 여러번 타게되면 결국 정점 i에서 다시 정점 i로 오는 경로가 시간 역행을 하게 된다.

이때 dp를 모두 0으로 초기화 하였는데, 이는 모든 정점에서 출발할 수 있기에 그렇게 했다. 이렇게 되면 음의 사이클 존재 여부만 알 수 있게 되고 출발점과 도착점이 특정이 되지 않아 정확한 값을 알기는 어려워진다.

만약 시작점이 특정된다면 해당 점에 대해서는 0으로 초기화하고 나머지 점은 최대값이나 float('inf') 등으로 초기화해주면 된다. 이렇게 하면 나머지 점에 대한 최소 경로를 알 수 있게된다.