[모각코] 210804 Today I Learned

<백준 1865번 - 웜홀>

 

ㅎ............

벨만포드....... 모르겠어요.........

오늘 낮에 벨만포드 다른 문제 풀다가 안 풀려서 넘기고 이거 푼 건데 그 문제를 못 풀어서 그런가 이것도 못 풀겠다.

내 벨만포드 코드에 문제가 있나보다..

뭐가 문제일까... 

 

근데 이 문제는 테스트 케이스 여러 개 받아와야 해서 for문 안에서 모든 것을 처리해야 하는데

그걸 이해하는데 오래 걸렸다. 문제가 너무 길어서 읽기 싫게 생겼거든요..

내일 다시 풀거나 다음 모각코 때 다시 풀어야지.... ㅠ

 

import sys
input = sys.stdin.readline

def bf(start):
    dist[start] = 0
    for i in range(1, n+1):
        for next, time in road[i]:
            if dist[i] != float('inf') and dist[next] > dist[i] + time:
                dist[next] = dist[i] + time
                if i == n-1: #n-1번 이후에도 값이 갱신되면 음수 사이클 존재.
                    return False
    return True

TC = int(input())
for i in range(TC):
    n, m, w = map(int, input().split())
    road = [[] for i in range(n+1)]
    wormhole = [[] for i in range(n+1)]
    dist = [float('inf') for i in range(n+1)]
    for j in range(m):
        s, e, t = map(int, input().split())
        road[s].append([e, t])
        road[e].append([s, t])
    for k in range(w):
        s, e, t = map(int, input().split())
        wormhole[s].append([e, -t])

    negative_cycle = bf(1)
    if not negative_cycle:
        print("NO")
    else:
        print("YES")

 

---

 

풀었다 !!!!

2021.08.05 - [Coding/백준] - [Python] 백준 1865번 - 웜홀