글 읽기 - [JAVA] 1504번 문제 도움 부탁드립니다.

kisrin4319 7년 전 0

다른 방식으로 구현해서 통과하긴 했습니다만 제가 짠 코드에 무슨 문제가 있나..? 싶어 도움부탁드립니다.

우선 순위큐 - 다익스트라 알고리즘을 이용해서 코드를 작성했습니다.

그리고 1 -> r1 -> r2 -> N, 1->r2->r1->N 경로를 3구간씩 나눠서 구간별 최소경로를 더해 마지막에 inf 보다 크면 -1, 작으면 최소 경로를 출력하게 했는데 제출 하자마자 거의 바로 틀렸습니다가 뜹니다.

inf 값에 의한 오버플로우는 아닌거 같은데 800001 뿐만 아니라 2400001 까지 해봐도 자꾸 그러네요 ㅠ

도움 부탁드립니다.

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

class MyScanner {
	BufferedReader br;
	StringTokenizer st;

	public MyScanner() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	String next() {
		while (st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt() {
		return Integer.parseInt(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	char nextChar() {
		return next().charAt(0);
	}
}

public class Main {

	public static PrintWriter out;
	public static int N,M;
	public static int[][] map;
	public static final int inf = 800001;
	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N+1][N+1];
		for(int r=1;r<N;r++)
		{
			for(int c=1;c<N;c++)
			{
				map[r][c] = r==c ? 0 : inf;
			}
		}
		for(int i=0;i<M;i++)
		{
			int t1 = sc.nextInt();
			int t2 = sc.nextInt();
			int t3 = sc.nextInt();
			map[t1][t2] = t3;
		}
		int r1 = sc.nextInt();
		int r2 = sc.nextInt();
		int result1 = 0;
		int result2 = 0;
		int[] vc;
		
		vc = dijkstra(1);
		result1+= vc[r1];
		result2+= vc[r2];
		
		vc = dijkstra(r1);
		result1+= vc[r2];
		result2+= vc[N];
		
		vc= dijkstra(r2);
		result1+= vc[N];
		result2+= vc[r1];
		
		
		if(Math.min(result1, result2)>=inf){
			out.println(-1);
		}
		else{
			out.println(Math.min(result1, result2));
		}
		out.flush();
	}
	private static int[] dijkstra(int start)
	{
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		int[] dist = new int[N+1];
		Arrays.fill(dist, inf);
		dist[start] = 0;
		
		q.offer(new Edge(start,dist[start]));
		
		while(!q.isEmpty())
		{
			Edge e = q.poll();
			int index = e.index;
			int cost = e.cost;
			
			if(cost>dist[index]) continue;
			
			for(int i=1;i<=N;i++){
				if(dist[i]> dist[index]+map[index][i])
				{
					dist[i]=dist[index]+map[index][i];
					q.offer(new Edge(i,dist[i]));
				}
			}
		}
		return dist;
	}

}

class Edge implements Comparable<Edge> {
	int index, cost;

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

	@Override
	public int compareTo(Edge e) {
		return cost <= e.cost ? -1:1 ;
	}
}

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

문제

문제

출처

ICPC

[JAVA] 1504번 문제 도움 부탁드립니다.

kisrin4319 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말