아이디어

• 1개의 다리는 가중치가 T인 S→E 간선과 E→S 간선으로 취급한다.
• 1개의 웜홀은 가중치가 -T인 S→E 간선으로 취급한다.
• 그래프가 음의 간선을 포함하므로 벨만-포드 알고리즘을 사용해야 한다.
  • 벨만-포드 알고리즘: 모든 간선을 V-1번 탐색하며 최솟값으로 거리를 갱신한다.
    • V-1번 탐색하는 이유: 사이클을 돌지 않을 때 임의의 두 정점을 연결하는 경로는 최대 V-1개의 간선을 지나간다.
• "한 점에서 출발해 되돌아왔을 때 시간이 되돌아가있는 경우" → 음수 사이클 여부 판단
• 음수 사이클 판단 방법 - V-1번 탐색 이후 한 번 더 모든 간선을 탐색 했을 때, 거리가 갱신이 되는 경우가 있으면 음수 사이클이 존재하는 것이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int INF = Integer.MAX_VALUE / 2;
	
	static int TC, N, M, W, S, E, T;
	static List<Edge> edgeList = new ArrayList<>();
	static int[] dist;

	public static void main(String[] args) throws Exception {
		TC = Integer.parseInt(rd.readLine());
		TC_LOOP: for (int tc = 1; tc <= TC; tc++) {
			tk = new StringTokenizer(rd.readLine());
			N = Integer.parseInt(tk.nextToken());
			M = Integer.parseInt(tk.nextToken());
			W = Integer.parseInt(tk.nextToken());
			
			edgeList.clear();
			dist = new int[N+1];
			
			for (int i=0; i<M; i++) {
				tk = new StringTokenizer(rd.readLine());
				S = Integer.parseInt(tk.nextToken());
				E = Integer.parseInt(tk.nextToken());
				T = Integer.parseInt(tk.nextToken());
				edgeList.add(new Edge(S, E, T));
				edgeList.add(new Edge(E, S, T));
			}
			for (int i=0; i<W; i++) {
				tk = new StringTokenizer(rd.readLine());
				S = Integer.parseInt(tk.nextToken());
				E = Integer.parseInt(tk.nextToken());
				T = Integer.parseInt(tk.nextToken());
				edgeList.add(new Edge(S, E, -T));
			}
			
			// bellman-ford
			dist[1] = 0;
			for (int i=2; i<=N; i++) dist[i] = INF;
			
			// N-1번 반복
			for (int i=0; i<N-1; i++) {			
				// 모든 간선 확인
				for (Edge e: edgeList) {
					dist[e.v2] = Math.min(dist[e.v2], dist[e.v1] + e.w);
				}
			}

			// N번째 반복에서 거리가 갱신되는 정점이 있다면 음수 사이클 존재
			for (Edge e: edgeList) {
				if (dist[e.v1] + e.w < dist[e.v2]) {
					sb.append("YES\n");
					continue TC_LOOP;
				}
			}
			
			sb.append("NO\n");
		}
		System.out.println(sb);
	}
	
	static class Edge {
		int v1, v2, w;
		Edge(int v1, int v2, int w) {
			this.v1 = v1;
			this.v2 = v2;
			this.w = w;
		}
	}
}

메모리와 시간

• 메모리: 36952 KB
• 시간: 660 ms

리뷰

• 처음에 '임의의 점'이라는 것에 낚여 모든 정점을 시작점으로 해서 탐색해야 하는 줄 알아 한참 헤맸다.