SPFA (Shortest Path Faster Algorithm)

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;


class Farm {
	int s;
	int e;
	int t;
	
	Farm (int s, int e, int t){
		this.s = s;
		this.e = e;
		this.t = t;
	}
}
public class SPFA {

	/*
	 * (중상) [연습P-0008] 웜홀 
	 * 
	 */
	
	

    public static void main(String[] args) throws IOException {
    	
    	System.setIn(new FileInputStream("res/seminar/wormhall.txt"));
        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 tIndex = 1; tIndex <= T; tIndex++){
        	ST = new StringTokenizer(br.readLine());
        	
        	int N = Integer.parseInt(ST.nextToken()); // 1 <= N <= 500
        	int M = Integer.parseInt(ST.nextToken()); // 1 <= M <= 2500
        	int W = Integer.parseInt(ST.nextToken()); // 1 <= W <= 200
        	
        	
        	ArrayList[] adjList = new ArrayList[N+1];
        	for (int i = 1; i <= N; i++){
        		adjList[i] = new ArrayList();
        	}
        	
        	//1. 농장통로 저장
        	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[s].add(new Farm(s, e, t));
        		adjList[e].add(new Farm(e, s, t));
        	}
        	
        	//2. 웜홀정보 저장
        	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[s].add(new Farm(s, e, -t));
        	}
        	
        	int[] dist = new int[N+1];						//누적거리
        	Arrays.fill(dist, Integer.MAX_VALUE-50000);		//초기화
        	
        	int[] cycle = new int[N+1];						//음수사이클 판별용
        	boolean[] inq = new boolean[N+1];				//큐 존재유무
        	Queue que = new LinkedList<>();		//큐 선언
        	
        	int root = 1;									//시작점 1
        	que.add(root);									//큐 저장
        	dist[root] = 0;									//시작점 거리 입력
        	inq[root] = true;								//큐 존재유무
        	cycle[root]++;									//음수사이클용
        	
        	
        	//3. SFPA
        	String result = "NO";
        	while(!que.isEmpty()){
        		boolean flag = false;						//음수사이클 체크용
        		
        		int cur = que.poll();
        		inq[cur] = false;
        		

        		for (Farm next : adjList[cur]){
        			int node = next.e;
        			int weight = next.t;
        			
        			if (dist[node] > dist[cur] + weight){	//누적거리 비교
        				dist[node] = dist[cur] + weight;
        				
        				cycle[node]++;			
        				if (cycle[node] >= N){				//업데이트가 N번이상 발생시 음수사이클
        					flag = true;
        					break;
        				}
        				
        				if (inq[node]) continue;
        				inq[node] = true;				 
        				que.add(node);
        			}
        		}
        		if (flag){									//음수사이클시 yes!
        			result = "YES";
        			break;
        		}
        	}
        	
        	bw.write("#"+tIndex+" "+result+"\n");
        }
        
        br.close();
        bw.flush();
        bw.close();
    }
}