벨만포드 알고리즘

boj 1865번 문제를 풀면서 공부한 알고리즘이다.
기존 bf알고리즘 조건을 변형해야 풀 수 있었는데 아래bf함수의 2중for문안의 if문에 조건하나를 삭제하여 풀 수 있었다. "d[curr] != inf"라는 조건을 넣으면 시작지점 부터의 정확한 최단시간을 얻을 수 있지만 1865문제는 시작지점이 주어지지 않고 음수 사이클 여부만 검사하면 되기에 이 조건을 제거하여 풀 수 있었다.

for _ in range(int(input())):
    n,m,w = [*map(int,input().split(' '))]
    info = []
    for i in range(m):
        s,e,t = [*map(int,input().split(' '))]
        info.append([s,e,t])
        info.append([e,s,t])
    for i in range(w):
        s,e,t = [*map(int,input().split(' '))]
        info.append([s,e,-t])
    def bf():
        inf = 2**99
        d = [inf for _ in range(501)]
        d[1] = 0
        for i in range(n):
            for curr,nxt,cost in info:
                if d[nxt] > d[curr] + cost:
                    if i == n - 1:
                        return True
                    d[nxt] = d[curr] + cost
        return False
    if bf():
        print("YES")
    else:
        print("NO")