글 읽기 - 1865 문제 시작지점 질문(정답코드 있음)

vywogns123 2년 전 0

벨만포드 알고리즘을 이용해서 문제를 풀었습니다. 34번째 줄을 보면 처음에는 시작지점을 1로 지정하여 돌렸을땐 '틀렸습니다'가 나오는데 시작지점을n으로 지정하여 돌리면 정답처리가 됩니다. 시작지점을 1로 두는 거랑 n으로 두는 거랑 차이가 있나요? 아니면 제가 벨만포드로직을 잘못이해하고 짠건가요?? ㅜㅜㅜㅜ

def bellman_ford(edges,dist):
    global n, m, w
    for _ in range(m+w-1):#간선의 개수-1 만큼 반복
        for now in range(1,n+1):
            for next in edges[now]:
                if dist[now] != 1e9 and dist[next[0]] > dist[now] + next[1]:
                    dist[next[0]] = dist[now] + next[1]
    # 음수사이클 확인
    for now in range(1,n+1):
        for next in edges[now]:
            if dist[now] != 1e9 and dist[next[0]] > dist[now] + next[1]:
                return True
    return False

import sys
input = sys.stdin.readline

ans = []
for _ in range(int(input().rstrip())):
    n, m, w = map(int,input().split())
    edges = [[] for _ in range(n+1)]
    # 도로 추가(양방향)
    for _ in range(m):
        s, e, t = map(int,input().split())
        edges[s].append((e,t))
        edges[e].append((s,t))
    # 웜홀 추가(단방향)
    for _ in range(w):
        s, e, t = map(int,input().split())
        edges[s].append((e,-t))
    
    dist = [1e9] * (n+1)
    dist[n] = 0
    #dist[1] = 0  => 틀림

    #벨만 포드 알고리즘 수행
    if bellman_ford(edges, dist):
        ans.append("YES")
        continue
    ans.append("NO")
for i in ans:
    print(i)