[Python]최단경로 백준 1865

문제

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

문제가 매우길다.

하지만 내용은 웜홀은 음의 간선이고 음의 사이클을 가지는 알아보면된다.

그런데 벨만포드 알고리즘은 출발노드와 도착노드가 정해져 있어야한다. 이문제는 모든

 출발점에서 확인해야한다.

원래의 시간복잡도 O(E*V)를 V만큼 다시 반복해줘야하는것이다.

주어진 시간을 봤을때 어림도 없다. 

SPFA라는 벨만포드를 개선한 알고리즘이 있지만 그것또한 최악의 경우 O(E*V)이기 때문

에 불가능하다.

질문을 조금 찾아보니 문제에 문제가 있는거같다.

출발지점을 정해주거나 모든  위치는 연결되어있다등의 추가 조건이 필요할거같다.

모든 노드를 검사하는 문제는 아니며 아마 출발지점을 1로 두었을때 일반적인 방법으로

 벨만포드알고리즘을 사용하면 해결되는 문제이다.

import sys
T=int(sys.stdin.readline())
 
for _ in range(T):
    N,M,W=map(int,sys.stdin.readline().split())#지점,도로의수,웜홀의수
    G=[]
    for _ in range(M):#양방향 도로 추가
        S,E,T=map(int,sys.stdin.readline().split())
        G.append([S,E,T])
        G.append([E,S,T])
 
    for _ in range(W):#웜홀 추가
        S,E,T=map(int,sys.stdin.readline().split())
        G.append([S,E,-T])
 
    INF=sys.maxsize
 
    # for i in range(N):
    result = [INF for _ in range(N + 1)]
    result[1] = 0
    for i in range(N):
        update = False#
        for j in range(2*M+W):
            S=G[j][0]#출발
            E=G[j][1]#도착
            T=G[j][2]#시간
            if result[S]!=INF and result[E]>result[S]+T:
                result[E]=result[S]+T
                update=True
                if i==N-1:
                    update=True
                    break
        if update==False:#n번 돌기전에 모든 최소거리가 정해졌다면
            break
 
    if update:
        print("YES")
    else:
        print("NO")