[백준] 1865 웜홀 [자바]

 

---

https://dragon-h.tistory.com/24?category=789780 

[백준 1865 : JAVA] 웜홀/ 벨만-포드

https://www.acmicpc.net/board/view/72996

글 읽기 - 데이터를 추가해 주세요.

 

※ 음수 사이클만 확인하면 되기 때문에 모든 시작점을 0으로 해놓고 벨만포드를 돌려야함.

    웜홀을 통과해 cost가 가장 적은 수(음수만) 를 dist에 저장해놓고 이것이 음수사이클을 발생시키는지 확인

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

class Road {
	int start;
	int end;
	int cost;
	public Road(int start, int end, int cost) {
		this.start = start;
		this.end = end;
		this.cost = cost;
	}
}

public class Main {
	static int[] dist;
	static Road[] road;
	static int INF = Integer.MAX_VALUE;
	static int n;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			dist = new int[n+1];
			road = new Road[2*m+w];
			Arrays.fill(dist, INF);
			int index = 0;
			int start = 0;
			for(int i = 0; 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());
				dist[s] = 0;
				dist[e] = 0;
				road[index++] = new Road(s,e,t);
				road[index++] = new Road(e,s,t);
			}
			for(int i = 0; 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());
				dist[s] = 0;
				road[index++] = new Road(s,e,t * -1);
			}
			if(bellmanford()) {
				sb.append("YES").append('\n');
			}
			else {
				sb.append("NO").append('\n');
			}
		}
		System.out.println(sb);
	}
	static boolean bellmanford() {
		for(int i = 0; i < n; i++) {
			for(Road roads : road) {
				if(dist[roads.start] != INF && dist[roads.start] + roads.cost < dist[roads.end]) {
					dist[roads.end] = dist[roads.start] + roads.cost;
				}
			}
		}
		for(Road roads : road) {
			if(dist[roads.start] != INF && dist[roads.start] + roads.cost < dist[roads.end]) {
				return true;
			}
		}
		return false;
	}
}