글 읽기 - 올리자 마자 틀리는데... 예외 케이스가 뭔지 모르겠네요..

filot 6년 전 0

서버에 올리자마 틀렸다고 하네요.

벨만포드로 풀었는데... 어떤 예외 케이스가 있는지 모르겠네요.

본문의 모든 예제는 잘 나오는데 ..

혹시 풀면서 더 고려한 케이스가 있었는데 힌트 좀 부탁드립니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int M;
	static int S;
	static int E;
	static int[] MONEY;
	static long INF = Long.MAX_VALUE;
	static long[] D;
	static List[] adjList;
	
	static String gg = "gg";
	static String Gee = "Gee";
	
	public static void main(String[] args) throws Exception {
        
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		
		StringTokenizer st1 = new StringTokenizer(reader.readLine());
		
		N = Integer.parseInt(st1.nextToken());
		S = Integer.parseInt(st1.nextToken());
		E = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());
		
		adjList = new List[N];
		
		for (int i = 0; i < N; i++)
			adjList[i] = new ArrayList<Vertex1219>();
		
		for (int i = 1; i <= M; i++) {
			StringTokenizer st2 = new StringTokenizer(reader.readLine());
			
			int u = Integer.parseInt(st2.nextToken());
			int v = Integer.parseInt(st2.nextToken());
			long w = Long.parseLong(st2.nextToken());
			
			adjList[u].add(new Vertex1219(v, w));
		}
		
		StringTokenizer st2 = new StringTokenizer(reader.readLine());
		MONEY = new int[N + 1];
		
		for (int i = 0; i < N; i++)
			MONEY[i] = Integer.parseInt(st2.nextToken());
		
		boolean hasNegativeCycle = bellmanFord();
	
		if (D[E] == INF)
			writer.println(gg);
		else if (hasNegativeCycle)
			writer.println(Gee);
		else
			writer.println(-D[E]);
		
		writer.close();
		reader.close();
	}
	
	private static boolean bellmanFord() {
		D = new long[N];
		Arrays.fill(D, INF);
		D[S] = -MONEY[S];
		
		for (int i = 1; i <= N - 1; i++) {
			for (int u = 0; u < adjList.length; u++) {
				List<Vertex1219> list = adjList[u];
				
				for (Vertex1219 v : list)
					if (D[v.u] > D[u] + v.w - MONEY[v.u])
						D[v.u] = D[u] + v.w - MONEY[v.u];
			}
		}
		
		for (int u = 0; u < N; u++) {
			List<Vertex1219> list = adjList[u];
			
			for (Vertex1219 v : list)
				if (D[v.u] > D[u] + v.w - MONEY[v.u])
					return true;
		}
		
		return false;
	}

}

class Vertex1219 {
	int u;
	long w;
	
	public Vertex1219(int u, long w) {
		this.u = u;
		this.w = w;
	}
}

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

문제

문제

출처

ICPC

올리자 마자 틀리는데... 예외 케이스가 뭔지 모르겠네요..

filot 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말