글 읽기 - 1865번 웜홀 문제 어디가 틀린지 모르겠습니다..

pjy1368 3년 전 0

벨만 포드 알고리즘을 활용해서 풀었는데 계속 9퍼센트에서 틀렸습니다가 뜹니다..

어디가 틀렸는지 궁금합니다.

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

class Road {
	int end;
	int weight;

	Road(int end, int weight) {
		this.end = end;
		this.weight = weight;
	}
}

public class Main {
	static int N, M, W;
	static int[] dist;
	static ArrayList<ArrayList<Road>> a;

	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 TC = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		while (TC-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());

			dist = new int[N + 1];
			a = new ArrayList<>();
			for (int i = 0; i <= N; i++) {
				a.add(new ArrayList<>());
			}

			for (int i = 0; i < M + W; i++) {
				st = new StringTokenizer(br.readLine());
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				int weight = Integer.parseInt(st.nextToken());

				if (i < M) {
					a.get(start).add(new Road(end, weight));
					a.get(end).add(new Road(start, weight));
				} else {
					a.get(start).add(new Road(end, -weight));
				}
			}

			sb.append(bellmanFord() ? "YES\n" : "NO\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	public static boolean bellmanFord() {
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[1] = 0;
		boolean update = false;
		
		for (int i = 1; i < N; i++) {
			update = false;
			for (int j = 1; j <= N; j++) {
				for (Road road : a.get(j)) {
					if (dist[j] != Integer.MAX_VALUE && dist[road.end] > dist[j] + road.weight) {
						dist[road.end] = dist[j] + road.weight;
						update = true;
					}
				}
			}

			if (!update) {
				break;
			}
		}

		if (update) {
			for (int i = 1; i <= N; i++) {
				for (Road road : a.get(i)) {
					if (dist[i] != Integer.MAX_VALUE && dist[road.end] > dist[i] + road.weight) {
						return true;
					}
				}
			}
		}

		return false;
	}

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1865번 웜홀 문제 어디가 틀린지 모르겠습니다..

pjy1368 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말