boj 1865: 웜홀

유사한 문제

2020/07/06 - [알고리즘 공부] - boj 11657: 타임머신

boj 11657: 타임머신

 

음수 사이클의 존재 여부를 찾는 문제이다.

주의할 점은 사이클이 웜홀을 포함하는지 여부이기 때문에 웜홀의 start가 시작점일때를 체크하도록 한다.

 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int testcase = in.nextInt();
		for (int t = 0; t < testcase; t++) {

			int n = in.nextInt();
			int m = in.nextInt();
			int w = in.nextInt();

			List<Hole> holes = new ArrayList<Hole>();

			for (int i = 0; i < m; i++) {
				int start = in.nextInt();
				int end = in.nextInt();
				int time = in.nextInt();
				holes.add(new Hole(start, end, time));
				holes.add(new Hole(end, start, time));
			}

			HashSet<Integer> startSets = new HashSet<Integer>();
			for (int i = 0; i < w; i++) {
				int start = in.nextInt();
				int end = in.nextInt();
				int time = in.nextInt();
				startSets.add(start);
				holes.add(new Hole(start, end, -time));
			}

			boolean isNegativeCycle = false;
			Iterator it = startSets.iterator();
			while (it.hasNext()) {
				long dist[] = new long[n + 1];
				Arrays.fill(dist, Long.MAX_VALUE);
				dist[(int) it.next()] = 0;

				for (int i = 1; i <= n; i++) {
					for (int j = 0; j < holes.size(); j++) {
						int start = holes.get(j).start;
						int end = holes.get(j).end;
						int time = holes.get(j).time;

						if (dist[start] != Long.MAX_VALUE && dist[end] > dist[start] + time) {
							dist[end] = dist[start] + time;
							if (i == n) {
								isNegativeCycle = true;
							}
						}
					}
				}
				if (isNegativeCycle) {
					break;
				}
			}
			if (isNegativeCycle) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}
}

class Hole {
	int start, end, time;

	public Hole(int start, int end, int time) {
		this.start = start;
		this.end = end;
		this.time = time;
	}
}