[백준][벨만포드] 1865. 웜홀

1865. 웜홀

1865번: 웜홀

 

• 내 풀이
  • 91퍼에서 시간초과
  • depth를 같이 넣어줘서 n번 넘게 돌아가면 멈춰주게 하려했지만 시간초과
  • 음수는 다익스트라로 불가능하기 때문에 벨만포드 써야함

from collections import deque


def bfs(start):
    tmp = [float('inf') for _ in range(n+1)]
    tmp[start] = 0
    queue = deque()
    queue.append((0, start))

    while queue:
        depth, s = queue.popleft()
        if depth >= n:
            break

        for e, t in graph[s]:
            if tmp[e] > tmp[s]+t:
                tmp[e] = tmp[s]+t
                if e == start and tmp[e] < 0:
                    break
                queue.append((depth+1, e))

    if tmp[start] < 0:
        return 1
    else:
        return 0


T = int(input())
for tc in range(T):
    n, m, w = map(int, input().split())
    graph = [[] for _ in range(n+1)]

    # 도로는 방향이 X
    for i in range(m):
        s, e, t = map(int, input().split())
        graph[s].append((e, t))
        graph[e].append((s, t))

    # 웜홀은 방향이 O
    for i in range(w):
        s, e, t = map(int, input().split())  # 줄어드는 시간
        graph[s].append((e, -t))

    result = [0 for _ in range(n+1)]
    answer = 0
    for i in range(1, n+1):
        answer += bfs(i)

    print('YES' if answer > 0 else 'NO')

 

 

• 다른 사람 풀이
  • 벨만포드
  • 음수 사이클이 존재하느지 확인하고 멈춰주기

from collections import deque


def bf(start):
    tmp = [10001 for _ in range(n+1)]
    tmp[start] = 0
    for i in range(1, n+1):
        for s in range(1, n+1):
            for e, t in graph[s]:
                if tmp[e] > tmp[s] + t:
                    tmp[e] = tmp[s] + t
                    if e == s and tmp[e] < 0:
                        return True
                    if i == n:  # n번 이후에도 값이 갱신되면 음수 사이클 존재.
                        return True
    return False


T = int(input())
for tc in range(T):
    n, m, w = map(int, input().split())
    graph = [[] for _ in range(n+1)]

    # 도로는 방향이 X
    for i in range(m):
        s, e, t = map(int, input().split())
        graph[s].append((e, t))
        graph[e].append((s, t))

    # 웜홀은 방향이 O
    for i in range(w):
        s, e, t = map(int, input().split())  # 줄어드는 시간
        graph[s].append((e, -t))

    result = [0 for _ in range(n+1)]
    answer = bf(i)

    print('YES' if answer else 'NO')