글 읽기 - 예외 케이스가 무엇이 있을까요?

filot 7년 전 0

10% 이상 넘어가면 틀리다고 하네요.

기본 로직은 PriorityQueue를 이용한 다익스트라입니다.

A, B를 꼭 방문을 해야 하므로

long dist1 = dijkstra(1, A) + dijkstra(A, B) + dijkstra(B, N);
long dist2 = dijkstra(1, B) + dijkstra(B, A) + dijkstra(A, N);

long Answer = Math.min(dist1, dist2);

위와 같이 1 -> A -> B -> N, 1 -> B -> A -> N인 경우에서 최단을 선택을 했는데

통과가 잘 안되네요..

고수님들의 조언을 부탁드립니다.

아래분들의 도음으로 오버플로우를 감안하고 A <-> B간 최단은 한번만 구해도 되니.. 그렇게 처리를 했는데

0%에서 틀리던게 14%까지는 가네요...

접근방법은 맞아 보이는데.. 답답하네요.

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.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main1504 {
	static int N;
	static int E;
	static int A;
	static int B;
	static List[] adjList;
	static long INF = 900000000;

	public static void main(String[] args) throws Exception {
		String file = "C:/workspace/algorithm/boj/Main1504.txt";
		System.setIn(new FileInputStream(file));

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

		String[] input = reader.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		E = Integer.parseInt(input[0]);

		adjList = new List[N + 1];

		for (int i = 1; i <= N; i++)
			adjList[i] = new ArrayList<Edge1504>();

		for (int i = 1; i <= E; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());

			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			long w = Long.parseLong(st.nextToken());

			adjList[u].add(new Edge1504(u, v, w));
			adjList[v].add(new Edge1504(v, u, w));
		}

		StringTokenizer st = new StringTokenizer(reader.readLine());
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());

		long between = dijkstra(A, B);
		long dist1 = dijkstra(1, A) + between + dijkstra(B, N);
		long dist2 = dijkstra(1, B) + between + dijkstra(A, N);

		long Answer = Math.min(dist1, dist2);

		writer.println(Answer >= INF ? -1 : Answer);

		writer.close();
		reader.close();
	}

	private static long dijkstra(int start, int end) {
		long[] dist = new long[N + 1];
		Arrays.fill(dist, INF);

		Queue<Edge1504> queue = new PriorityQueue<Edge1504>();

		dist[start] = 0;
		queue.offer(new Edge1504(start, start, dist[start]));

		while (!queue.isEmpty()) {
			Edge1504 u = queue.poll();

			if (u.u == end)
				break;

			if (u.w > dist[u.v])
				continue;

			List<Edge1504> list = adjList[u.v];
			for (Edge1504 v : list) {
				if (dist[v.v] > dist[v.u] + v.w) {
					dist[v.v] = dist[v.u] + v.w;
					queue.offer(new Edge1504(v.u, v.v, v.w));
				}
			}
		}

		return dist[end];
	}
}

class Edge1504 implements Comparable<Edge1504> {
	int u;
	int v;
	long w;

	public Edge1504(int u, int v, long w) {
		this.u = u;
		this.v = v;
		this.w = w;
	}

	@Override
	public int compareTo(Edge1504 o) {
		return Long.compare(this.w, o.w);
	}
}

kkw564 7년 전 0

dist의 형이 int네요

long이어야 하지 않을까요?

cocomo1316 7년 전 0

1. A와 B 사이의 거리는 어디서 출발해도 같습니다.

2. 마지막 출력할 때 dijkstra는 int를 반환하기 때문에 dist1, dist2를 구할 때 (long) 캐스팅이 필요할 것 같습니다.

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

문제

문제

출처

ICPC

예외 케이스가 무엇이 있을까요?

filot 7년 전 0

kkw564 7년 전 0

cocomo1316 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말