글 읽기 - 1753번 출력초과가 뜹니다.

sothicly 6년 전 0

안녕하세요.

1753번 질문입니다.

예제에서는 분명히 잘 돌아가는데, 출력초과로 해결을 못하고 있습니다.

답변 주시면 정말 감사하겠습니다. 좋은 하루 보내세요.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static ArrayList<int[]> graph[];
	static int[] dist;

	public static void main(String[] args) throws IOException {

		int V, E;
		int start;
		int u, v, w;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(br.readLine());

		dist = new int[V + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;

		graph = new ArrayList[V + 1];
		for (int i = 1; i <= V; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int i = 0; i < E; i++) {

			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());

			int temp[] = { v, w };
			graph[u].add(temp);

		}

		dijkstra(start);

		for (int i = 1; i < dist.length; i++) {
			if (dist[i] == Integer.MAX_VALUE) {
				bw.write("INF" + "\n");
			} else {
				bw.write(dist[i] + "\n");
			}

		}

		bw.flush();
		br.close();
		bw.close();

	}

	private static void dijkstra(int start) {

		int vertex, distance;

		PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}

		});

		for (int i = 1; i <= graph.length - 1; i++) {

			int info[] = new int[2];

			info[0] = i;
			if (i == start) {
				info[1] = 0;
			} else {
				info[1] = Integer.MAX_VALUE - 1;
			}

			heap.add(info);
		}

		while (!heap.isEmpty()) {

			int[] data = heap.poll();

			vertex = data[0];
			distance = data[1];

			if (distance <= dist[vertex]) {

				for (int[] k : graph[vertex]) {

					int to = k[0];
					int edge = k[1];

					if (distance + edge < dist[to]) {
						dist[to] = distance + edge;
						int[] q = { edge, dist[to] };
						heap.add(q);
					}
				}
			}
		}
	}
}

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

문제

문제

출처

ICPC

1753번 출력초과가 뜹니다.

sothicly 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말