[백준] 1865번: 웜홀 (retry) Bellman ford template

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

initial

bellman works with negative weights, something which dijkstra is limited in. It works by updating the distance list for the cost to that node as minimal for n-1th iter time. Then when you iterate for the nth iter last time, if any of the value in the distance list can be reduced again, that means there is a negative cycle because we can add negative weights that reduce the distance to that specific node via a cycle.

basically the distance list in bellman ford also represents the cost to travel to that node (which is the index). But if there is a negative weight that forms a negative cycle (not just regular negative weights), then this distance list will have values that keep on decreasing, which is identified at i=n-1 step.

i tried impl but it is wrong and idk why it is wrong tbc

import sys
input = sys.stdin.readline


def bellman():
    distance = [10001 for _ in range(a+1)]
    distance[1]=0
    for i in range(a):
        for route in graph:
            start,end,cost = route
            if distance[start]+cost<distance[end]:
                distance[end]=distance[start]+cost
                if i==a-1:
                    return True
    return False

t=int(input())
for _ in range(t):
    a,b,c = map(int,input().split())
    graph=[]
    for _ in range(b):
        x,y,z = map(int,input().split())
        graph.append([x,y,z])
        graph.append([y,x,c])
    for _ in range(c):
        h,k,l = map(int,input().split())
        graph.append([h,k,-l])
    if bellman():
        print("YES")
    else:
        print("NO")

solution

from sys import stdin

input = stdin.readline

def bf():
    # inf를 사용하지 않고 임의의 큰 수 사용
    D = [200000000] * (N+1)
    # 어느 점을 기준으로 해도 상관없음
    D[1] = 0

    # N번 검사 
    for i in range(N):
        for rou in route:
            start, goal, time = rou
            if D[goal] > D[start] + time:
                D[goal] = D[start] + time
                # N번 시행시 갱신된다면, 음의 가중치 판단.
                if i == N-1:
                    return 'YES'
    return 'NO'


# 변수 입력
TC = int(input())

for _ in range(TC):
    N, M, W = map(int,input().split())
    route = []
    for _ in range(M):
        a, b, t = map(int,input().split())
        route.append([a,b,t])
        route.append([b,a,t])

    for _ in range(W):
        s, e, t = map(int,input().split())
        route.append([s,e,-t])


    print(bf())

complexity

ve time? it is less eff than dijkstra right

Time Complexity:

• The algorithm performs Bellman-Ford on the graph, which has a time complexity of O(N * (M + W)), where N is the number of vertices, M is the number of bidirectional roads, and W is the number of wormholes.
• In the worst case, the algorithm iterates N times, and in each iteration, it checks all edges (M + W). Therefore, the time complexity is O(N * (M + W)).

Space Complexity:

• The space complexity is O(N) for storing the distance array D.

Overall, the time and space complexities are both O(N * (M + W)).