글 읽기 - 예제 입력은 맞으나 틀린 결과를 출력합니다.

tjdgnsqn3 5년 전 0

나무위키에 올라온 다익스트라 설명을 보고, 코드를 작성했습니다.

Integer.MAX_VALUE를 넣었다가. 출력 초과가 출력돼서, 다음과 같이 코드를 변겅했었습니다.

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


class Node implements Comparable<Node>{

    public int V,W;

    public Node(int V, int W){
        this.V = V; // U -> V 할때 V
        this.W = W; // U -> V 의 가중치
    }

    @Override
    public int compareTo(Node arg0) { 
        return this.W - arg0.W; // 오름차순 정렬
    }
}
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // Node 개수와 엣지 개수를 입력받음
        String str1[] = br.readLine().split(" ");
        int V = Integer.parseInt(str1[0]);
        int E = Integer.parseInt(str1[1]);

        PriorityQueue<Node> edges[] = new PriorityQueue[V+1];
        Queue<Integer> tempQueue = new LinkedList<>();
        for(int i = 1; i<=V; i++)
            edges[i] = new PriorityQueue<>();
        
        // 시작 정점 입력받고, 가중치 배열 생성
        int K = Integer.parseInt(br.readLine());
        int W[] = new int[V+1];
        Arrays.fill(W, 9898798);
        W[K] = 0;
        // 시작정점 담아준다.

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

            String str2[] = br.readLine().split(" ");
            int u = Integer.parseInt(str2[0]);
            int v = Integer.parseInt(str2[1]);
            int w = Integer.parseInt(str2[2]);

            edges[u].offer(new Node(v, w));
        }
        
        for(int i = 1; i<=V; i++){
            tempQueue.offer(i);        
        }

        while(!tempQueue.isEmpty()){
            int s = tempQueue.poll(); // 시작
            Iterator it = edges[s].iterator();
            while(it.hasNext()){
                Node tempNode = (Node) it.next();
                W[tempNode.V] = Math.min(tempNode.W + W[s], W[tempNode.V]);
            }
        }

        // 값 출력
        for(int i = 1; i<=V; i++){
            if(W[i] == 9898798)
                bw.write("INF");
            else
                bw.write(String.valueOf(W[i]));
            bw.write("\n");
        }

        bw.flush();

    }
}

tjdgnsqn3 5년 전 0

tempQueue의 offer 방식을 좀 바꾸니 되더군요.

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

문제

문제

출처

ICPC

예제 입력은 맞으나 틀린 결과를 출력합니다.

tjdgnsqn3 5년 전 0

tjdgnsqn3 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말