글 읽기 - 1916번 다익스트라 inf값

skrek269 5년 전 0

이 소스에서

처음에 정의한 inf값이 Integer.MAX_VALUE-1 이면 틀리게 나오고

1000000000 이면 정답으로 나오는데 그 이유가 무엇인지 모르겠어요.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {	
	//다익스트라 
	static final int inf = Integer.MAX_VALUE-1;
    //inf값이 1000000000이면 정답
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		ArrayList<Edge>[] li = new ArrayList[n+1];
		for(int i=1;i<=n;i++) {
			li[i] = new ArrayList<Edge>();
		}
		boolean[] check = new boolean[n+1];

		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			li[x].add(new Edge(y,z));
		}
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		int[] dist = new int[n+1];
		Arrays.fill(dist,inf);
		dist[start]=0;
		for(int k=0;k<n-1;k++) {
			m = inf+1;
			int x = -1;
			//check[i]==false 이면서 dist[i]가 가장 작은 값을 선택
			for(int i=1;i<=n;i++) {
				if(!check[i] && m>dist[i]) {
					m = dist[i];
					x=i;
				}
			}
			check[x] = true;
			//x와 연결된 간선을 대상으로 dist 값을 갱신한다
			for(Edge edge : li[x]) {
				int y = edge.to;
				if(dist[y]>dist[x] + edge.cost) {
					dist[y] = dist[x] + edge.cost;
				}				
			}			
		}
		System.out.println(dist[end]);
	}
}
class Edge{
	int to,cost;
	public Edge(int a, int b ) {
		to = a;
		cost = b;
	}
}

djm03178 5년 전 2

다음과 같은 입력에서 오버플로가 발생하기 때문입니다.

skrek269 5년 전 0

예로 들어주신 케이스를 풀어보니 이해가 됐어요.

감사합니다.

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

문제

문제

출처

ICPC

1916번 다익스트라 inf값

skrek269 5년 전 0

djm03178 5년 전 2

skrek269 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말