글 읽기 - 어느 부분에서 틀린지 모르겠습니다..

jymaeng95 2년 전 0

다익스트라 알고리즘을 이용해서 해당 문제를 풀어봤는데

어느 부분에 문제가 있는지 잘 모르겠습니다..

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static class Node implements Comparable<Node> {
        private int node;
        private int dist;

        public Node(int node, int dist) {
            this.node = node;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.dist, o.dist);
        }
    }

    private static int V, E, startVertex;
    private static ArrayList<ArrayList<Node>> graph;
    private static boolean[] visited;
    private static int[] distance;
    private static final int INF = (int) 1e9;

    public static void main(String[] args) throws IOException {
        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());

        startVertex = Integer.parseInt(br.readLine());
        graph = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            graph.get(start).add(new Node(end, dist));
        }
        visited = new boolean[V + 1];
        distance = new int[V + 1];
        Arrays.fill(distance, INF);
        dijkstra(startVertex);
        for (int i = 1; i <= V; i++) {

            if (distance[i] == INF) {
                bw.write("INF");
                continue;
            }
            bw.write(String.valueOf(distance[i]));
            bw.newLine();
        }
        br.close();
        bw.close();
    }

    private static void dijkstra(int startVertex) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        distance[startVertex] = 0;
        pq.offer(new Node(startVertex, 0));
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            if (visited[node.node])
                continue;
            visited[node.node] = true;
            for (Node nd : graph.get(node.node)) {
                if (!visited[nd.node] && distance[nd.node] > distance[node.node] + nd.dist) {
                    distance[nd.node] = distance[node.node] + nd.dist;
                    pq.offer(new Node(nd.node, distance[nd.node]));
                }
            }
        }
    }
}

kdh6429 2년 전 1

이미 방문한 노드라도 더 작은값으로 갱신할수 있으면 재방문 해야합니다.

jymaeng95 2년 전 0

kdh6429 감사합니다!! 방문한 노드에서 작은 값을 처리하는것도 문제인것을 확인했고,,

30%에서 계속 틀렸다고 나오는 것이 이상해서 코드를 다시 확인하니 55번째 줄 bw,write('INF")를 하고 continue를 하는 바람에 newLine을 건너뚠 부분도 문제였습니다..

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

문제

문제

출처

ICPC

어느 부분에서 틀린지 모르겠습니다..

jymaeng95 2년 전 0

kdh6429 2년 전 1

jymaeng95 2년 전 0

kdh6429 감사합니다!! 방문한 노드에서 작은 값을 처리하는것도 문제인것을 확인했고,,

30%에서 계속 틀렸다고 나오는 것이 이상해서 코드를 다시 확인하니 55번째 줄 bw,write('INF")를 하고 continue를 하는 바람에 newLine을 건너뚠 부분도 문제였습니다..

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말