BOJ 1865번: 웜홀

www.acmicpc.net/problem/1865

1865번: 웜홀

아이디어:

벨만-포드 알고리즘을 구현하여 푸는 문제는 맞는데, 조건을 따질 게 좀 있어서 헤맸다.

1. N, M, W를 TC for 문 안에서 받아야 하는데 바보처럼 밖에서 받음.

2. 도로는 양방향이고, 웜홀은 단방향임..

3. 음수 사이클이 어디서 시작하는 지는 상관없이 존재 유무만 판단하는 것이므로, 1에서만 탐색하면 안되고 방문하지 않은 모든 정점을 탐색해야 함.

 

import sys

TC = int(sys.stdin.readline())
INF = 10**9
for _ in range(TC):
    N, M, W = map(int, sys.stdin.readline().split())
    road = [[] for _ in range(N+1)]
    hole = [[] for _ in range(N+1)]
    dist = [INF]*(N+1)
    for _ in range(M):
        S, E, T = map(int, sys.stdin.readline().split())
        road[S].append([E,T])
        road[E].append([S,T])
    for _ in range(W):
        S, E, T = map(int, sys.stdin.readline().split())
        hole[S].append([E,-T])

    flag = False
    for s in range(1, N+1):
        if dist[s]==INF:
            dist[s] = 0
            for i in range(1, N+1):
                for j in range(1,N+1):
                    if (dist[j]==INF): continue
                    for adj in road[j]:
                        if (dist[j]+adj[1]<dist[adj[0]]):
                            if (i==N):
                                flag = True
                                break
                            dist[adj[0]] = dist[j]+adj[1]
                    for adj in hole[j]:
                        if (dist[j]+adj[1]<dist[adj[0]]):
                            if (i==N):
                                flag = True
                                break
                            dist[adj[0]] = dist[j]+adj[1]
    if (flag==True):
        print('YES')
    else:
        print('NO')