글 읽기 - 특적한 최단 경로 다익스트라 질문

hsna7024 7년 전 0

안녕하세요.

다익스트라로

1 -> V1 - > V2 - > N

1 -> V2 -> V1 -> N

2개의 값중 작은 값으로 출력하게 풀이 하였습니다.

질문을 검색해보니 결과값을 더할때 범위가 벗어날 수 있다고

ans 타입을 long으로 변경해도 오답으로 나옵니다.

다익스트라도 기존에 풀이했던거랑 차이가 없어서 틀리지 않은것 같은데

어디가 잘못 됐는지 못찾고 있습니다.

도와주시면 감사하겠습니다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	static int n; // 정점 수
	static ArrayList<Edge> [] list;
	static final int INF = 987654321;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int m = sc.nextInt(); // 간선 수
		list = new ArrayList[n + 1];
		for(int i = 1; i <= n; i++)
			list[i] = new ArrayList<Edge>();
		
		for(int i = 0; i < m; i++){
			int u = sc.nextInt();
			int v = sc.nextInt();
			int c = sc.nextInt();
			list[u].add(new Edge(v, c));
			list[v].add(new Edge(u, c));
		}
		int v1 = sc.nextInt();
		int v2 = sc.nextInt();
		int [] distanceStart = dijkstra(1);
		int [] distanceV1 = dijkstra(v1);
		int [] distanceV2 = dijkstra(v2);
		
		long ans = distanceStart[v1] + distanceV1[v2] + distanceV2[n];
		long ans2 = distanceStart[v2] + distanceV2[v1] + distanceV1[n];
		
		if(ans > ans2){
			ans = ans2;
		}
		if(ans >= INF) {
			ans = -1;
		}
		System.out.println(ans);
		sc.close();

	}
	
	public static int [] dijkstra(int start){
		boolean [] visited = new boolean [n + 1];
		int [] distance = new int [n + 1];
		
		for(int i = 1; i <= n ; i++)
			distance[i] = INF;
		distance[start] = 0;
		for(int i = 0; i < n - 1; i++){
			int min = INF + 1;
			int x = -1;
			for(int j = 1; j <= n; j++){
				if(visited[j] == false && min > distance[j]) {
					min = distance[j];
					x = j;
				}
			}
			visited[x] = true;
			for(int j = 0; j < list[x].size(); j++){
				Edge edge = list[x].get(j);
				if(distance[edge.to] > distance[x] + edge.cost){
					distance[edge.to] = distance[x] + edge.cost;
				}
			}
		}
		return distance;
	}

}

class Edge{
	int to;
	int cost;
	public Edge(int to, int cost){
		this.to = to;
		this.cost = cost;
	}
}

alibaba 6년 전 1

여기도 각 노드상에 못찾아 가능 경우가 있기 때문에 더하기 전해 예외 처리 하시면 될거 같습니다.

hsna7024 6년 전 0

alibaba 님 감사합니다. 말씀대로 수정하니 통과하였습니다.

그런데 이해가 잘 안되는데 못찾아가는 거리값은 INF 값으로 받을 것이고 최대값인 3*INF도 long에 담기고 있는데

나중에 -1 처리하는 값은 왜 로직이 안맞는건가요

더하기전에 -1 하는것이나 더한 후 INF 넘어가는 값을 -1 처리하나 같은거 같은데

잘못생각하고 있는건가요?

		long ans;
		long ans2;
		if(distanceStart[v1] == INF || distanceV1[v2] == INF || distanceV2[n] == INF)
			ans = -1;
		else
			ans = distanceStart[v1] + distanceV1[v2] + distanceV2[n];
		if(distanceStart[v2] == INF || distanceV2[v1] == INF || distanceV1[n] == INF)
			ans2 = -1;
		else
			ans2 = distanceStart[v2] + distanceV2[v1] + distanceV1[n];
		
		if(ans > 0 && ans2 > 0 && ans > ans2){
			ans = ans2;
		}
		else if(ans < 0 && ans2 > 0)
			ans = ans2;

hyseokim 5년 전 0

int 끼리 더하고 나서 자료형을 변환 하기 때문에 더하기 전에 자료형 변환을 해주어야 합니다.

long ans = (long)distanceStart[v1] + distanceV1[v2] + distanceV2[n];

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

문제

문제

출처

ICPC

특적한 최단 경로 다익스트라 질문

hsna7024 7년 전 0

alibaba 6년 전 1

hsna7024 6년 전 0

hyseokim 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말