[백준]1865 웜홀

1. 풀이

그래프에서 음의 사이클이 단 하나라도 있으면 벨만포드의 V번째 반복에서 최솟값(nodeDist)의 갱신이 일어난다.

따라서 웜홀의 유무는 벨만포드 알고리즘을 이용하여 풀 수 있다

​

2. 주의사항

1. 도로는 양방향임

2. 도로와 웜홀은 모두 연결되어있다고 가정.(여러개의 컴포넌트 tc가 현재까진 없음)

현재 알고리즘은 임의의 점(1번노드) 하나를 잡아서 연결된 모든 노드들까지의 최단거리를 구한다. 따라서 임의의 시작점과 연결되어있는 그 음의 사이클만 확인할 수 있다.

아래가 반례이다. TRUE가 나와야 하지만 음의사이클이 시작점과 연결되어있지않아 음의사이클을 검출하지못하고 FALSE가나옴

<반례>

1
5 1 3
1 2 3
3 4 1
4 5 1
5 3 1

따라서 위의 경우(연결되어있진 않지만 음의 사이클을 확인해주기)를 해결하기 위해 소스코드 중

            #이부분을 생략하면 반례도 통과
            if nodeDist[n1]==maxNum:
                continue

위부분을 생략하면 연결되어있지 않는 곳에서 음의 사이클이 발생시 이를 발견할 수 있다. 하지만 아직 TC가 없기 때문에 그냥 벨만포드 정석대로 추가 후 코드작성.

 

3. 소스코드

maxNum=987653210

def bellman():
    nodeDist=[maxNum for i in range(N+1)]
    nodeDist[1]=0
    isUpdate=False
    #총 V-1번 수행
    for i in range(N):
        isUpdate=False
        for n1,n2,cost in edge:
            #모두 연결아니면 아래생략으로 답찾기 가능
            if nodeDist[n1]==maxNum:
                continue
            nowDist=nodeDist[n1]+cost
            if nowDist<nodeDist[n2]:
                isUpdate=True
                nodeDist[n2]=nowDist
    return isUpdate


T=int(input())
for t in range(T):
    N,M,W=map(int,input().split())
    edge=[]
    for m in range(M):
        S,E,T=map(int,input().split())
        edge.append([S,E,T])
        edge.append([E,S,T])
    for w in range(W):
        S,E,T=map(int,input().split())
        edge.append([S,E,-T])
    if bellman():
        print("YES")
    else:
        print("NO")