1865: 웜홀

풀이 시간

• 42m
• bellman-ford 알고리즘에 대해 공부한 후 풂

구현 방식

• bellman-ford 알고리즘
  -> 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점들까지의 최단 거리를 구할 수 있음
  -> 음의 사이클의 존재 여부를 알 수 있음
• "한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는 지 없는 지" -> bellman-ford 알고리즘을 통해 음의 사이클의 존재여부를 확인하면 된다

코드

import sys


def bellman_ford(graph, start):
    dist = dict()
    for node in graph:
        dist[node] = int(1e9)
    dist[start] = 0

    for i in range(N):
        for node in graph:
            for element in graph[node]:
                nnode, cost = element
                if dist[nnode] > dist[node] + cost:
                    dist[nnode] = dist[node] + cost
                    if i == N-1:
                        return True
    return False


TC = int(sys.stdin.readline()[:-1])
for _ in range(TC):
    N, M, W = map(int, sys.stdin.readline()[:-1].split())
    graph = dict()
    for m in range(M):
        S, E, T = map(int, sys.stdin.readline()[:-1].split())
        if S in graph: graph[S].append((E, T))
        else: graph[S] = [(E, T)]
        if E in graph: graph[E].append((S, T))
        else: graph[E] = [(S, T)]

    for w in range(W):
        S, E, T = map(int, sys.stdin.readline()[:-1].split())
        if S in graph: graph[S].append((E, -T))
        else: graph[S] = [(E, -T)]


    possible = bellman_ford(graph, 1)
    if possible: print("YES")
    else: print("NO")

결과

• 처음에는 모든 노드에 대해 최단거리를 구하면서 하나의 노드(i)마다 distance[i]가 음수인 경우가 있다면 "YES"를 출력해주는 방식으로 진행하였으나, 시간초과가 발생했다
• 이 문제는 아무 노드에서부터 bellman-ford를 시행하여 음의 사이클의 존재여부만 확인해주면 되는 문제였다 (초반에 조금 헷갈렸던 게 음의 사이클이 없으나 시간이 역행하는 정점이 없다면 "NO"를 출력해야하는 게 아닌가? 하는 의문이 들었다. 근데 문제 조건에 W는 1 이상이기 때문에 그런 경우는 생각할 필요가 없다~)