벨만포드

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_1865_belman {
	/*
	 * 웜홀
	 * https://www.acmicpc.net/problem/1865
	 * 벨만포드, SPFA
	 */
	static class Node {
		int s;
		int e;
		int w;
		
		Node (int s, int e, int w){
			this.s = s;
			this.e = e;
			this.w = w;
		}
	}
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for (int ti = 1; ti <= T; ti++) {
			
			st = new StringTokenizer(br.readLine());
			
			int N = Integer.parseInt(st.nextToken());	//지점
			int M = Integer.parseInt(st.nextToken());	//도로갯수
			int W = Integer.parseInt(st.nextToken());	//웜홀갯수
			
			
			ArrayList adjList = new ArrayList();
			for (int i = 1; i <= M; i++) {
				st = new StringTokenizer(br.readLine());
				
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int t = Integer.parseInt(st.nextToken());
				
				adjList.add(new Node(s, e, t));
				adjList.add(new Node(e, s, t));
			}
			
			for (int i = 1; i <= W; i++) {
				st = new StringTokenizer(br.readLine());
				
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int t = Integer.parseInt(st.nextToken());
				
				adjList.add(new Node(s, e, -t));
			}
			
			
			int[] dist = new int[N+1];
			Arrays.fill(dist, Integer.MAX_VALUE);
			dist[1] = 0;
			
			String ans = "NO";
			inf:for (int i = 1; i <= N; i++) {
				for (Node nxt : adjList) {
					if (dist[nxt.s] == Integer.MAX_VALUE) continue;
					if (dist[nxt.e] > dist[nxt.s]+nxt.w) {
						dist[nxt.e] = dist[nxt.s]+nxt.w;
						
						if (i == N) {
							ans = "YES";
							break inf;
						}
					}
				}
			}
			
			bw.write(ans+"\n");
			
		}
			
		
		br.close();
		bw.flush();
		bw.close();
	}

}