글 읽기 - 자바 출력초과 정말 이유를 모르겠어요 ㅠㅠ 도와주세요

youmustbeharrypotter 4년 전 0

혹시 제가 간과한 부분이 있다면 ,가르쳐주시면 감사하겠습니다.

일단 질문게시판에 있는 예제들은 모두 잘 돌아가고요 , 벨만포드 알고리즘을 그대로 구현했습니다 ㅜㅜ

진짜 별의 별짓 다해봤는데 계속 출력초과만 나오네요..

많은 분들이 말씀하시던 "같은 간선이 여러개 있을 때, 음수 가중치가 더 큰 가중치에 덮어씌여진다" 는

인접리스트로 구현해서 해당이 안되는 이야기 같구요 ..

혹시 벨만포드를 잘못 이해한걸까요 ? ?

가르쳐 주신다면 감사하겠습니다 ㅜ ㅜ

import java.io.*;
import java.util.*;

class Graph //edge 정보 객체배열로 저장 
{
	Graph(int src, int dest ,int weight){
		this.src=src;
		this.dest=dest;
		this.weight=weight;
	}
	int src; //from
	int dest; //to 
	int weight;  //가중치 
}


public class Main {
	private static final int INF = 1000000000; 
	private static int N; //도시 개수 
	private static int M; //버스 노선 개수 
	private static Graph[] edge; //엣지 저장 
	private static int[] dist; //노드 1로부터 각각의 노드 까지의 최단경로 저장
   public static void main(String[] args) throws IOException{		
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   StringTokenizer stk = new StringTokenizer(br.readLine());
	   N = Integer.parseInt(stk.nextToken());
	   M = Integer.parseInt(stk.nextToken());
		dist = new int[N+1]; //초기화 
		edge = new Graph[M]; //초기화 
		for(int i=0; i<M;i++) { //간선 입력 
			stk = new StringTokenizer(br.readLine());
			int src = Integer.parseInt(stk.nextToken());
			int dest = Integer.parseInt(stk.nextToken());
			int weight = Integer.parseInt(stk.nextToken());
			edge[i]=new Graph(src,dest,weight);
		}
		Arrays.fill(dist, INF); //초기화 
		dist[1]=0; //출발 노드 초기화 
		if(bellmanFord()==false) { //음수 사이클 있음 
			System.out.println("-1");
		}
		else { //음수 사이클 없음 
			for(int i = 2; i<=N; i++) {
				if(dist[i]==INF) {
					System.out.println("-1"); //연결 되어 있지 않음 
				}
				else {
					System.out.println(dist[i]); //최단경로 출력 
				}
			}
		}
	}
	
	
	public static boolean bellmanFord() {
		for(int i = 1; i<=N-1; i++) { // 정점 수 -1 
			for(int j=0;j<M; j++) { //간선수 M 
				int u =edge[j].src; //from
				int v=edge[j].dest; //to 
				int w=edge[j].weight; //가중치
				//dist[u]가 구해졌음 && dist[v]가 dist[u] + v의 가중치보다 크면 
				if(dist[u]!=INF && dist[v] > dist[u]+w) {
					dist[v] = dist[u]+w; //갱신 
				}
			 }
			} 
		
		for(int j=0; j<M; j++) { //음수사이클 다시한번 확인 	
			int u = edge[j].src; //from
			int v= edge[j].dest; //to 
			int w = edge[j].weight; //가중치 
			if( dist[u]!=INF && dist[v] > dist[u]+w) {
				return false; //값이 또 적게 변할 수 있다면 계속 변하는 음수사이클이 있다는 것. 따라서 false 리턴 
			}
		}
		return true; //음수사이클 없음 
		
	}
}

bupjae 4년 전 7

이 문제에서의 "출력초과"는 "-1"을 출력해야 할 입력 데이터를 답이 있는 걸로 잘못 판단해서 출력하려고 시도했기 때문일 겁니다.

이 문제는 입력 데이터에 따라 inf 가 의미가 없거나 정수 overflow 를 일으킬 수 있습니다.

아래 데이터는 음의 사이클이 있기 때문에 -1 하나만 출력해야 합니다.

youmustbeharrypotter 4년 전 0

오버플로 처리하니까 해결되었습니다!! 정말 감사합니다!!ㅠㅠ

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

문제

문제

출처

ICPC

자바 출력초과 정말 이유를 모르겠어요 ㅠㅠ 도와주세요

youmustbeharrypotter 4년 전 0

bupjae 4년 전 7

youmustbeharrypotter 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말