글 읽기 - Java 시간 초과 (다익스트라)

rlaxodnd5 4년 전 0

다익스트라로 통과할꺼라 생각했는데 안되네요..

로직의 문제인지 확인 부탁드림다 ㅠ

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

public class Main {
    private static List<Edge>[] edges;
    private static int[] paths;

    private static final int INF = Integer.MAX_VALUE;

    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());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        edges = new List[V+1];
        paths = new int[V+1];

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

        int K = Integer.parseInt(br.readLine());

        for (int i = 0; i < E; i++) {
            String[] strs = br.readLine().split("\\s");

            int src = Integer.parseInt(strs[0]);
            int dest = Integer.parseInt(strs[1]);
            int cost = Integer.parseInt(strs[2]);

            edges[src].add(new Edge(dest, cost));
        }

        PriorityQueue<Path> q = new PriorityQueue<>(V, Path::compareTo);
        q.add(new Path(K, 0));

        while(!q.isEmpty()) {
            Path top = q.poll();
            int cdest = top.dest;
            int cdist = top.dist;

            if(cdist >= paths[cdest])
                continue;

            paths[cdest] = cdist;

            for(Edge e : edges[cdest]) {
                int ndest = e.dest;
                int ndist = cdist + e.cost;

                if(ndist >= paths[ndest])
                    continue;

                q.add(new Path(ndest, ndist));
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= V; i++) {
            int dist = paths[i];
            if(dist < INF)
                sb.append(dist);
            else
                sb.append("INF");
            sb.append('\n');
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static class Edge {
        private int dest;
        private int cost;

        private Edge(int dest, int cost) {
            this.dest = dest;
            this.cost = cost;
        }
    }

    private static class Path {
        private int dest;
        private int dist;

        private Path(int dest, int dist) {
            this.dest = dest;
            this.dist = dist;
        }

        private static int compareTo(Path a, Path b) {
            return Integer.compare(b.dist, a.dist);
        }
    }
}

lobo_prix 4년 전 1

return Integer.compare(a.dist, b.dist);

rlaxodnd5 4년 전 0

감사합니다!

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

문제

문제

출처

ICPC

Java 시간 초과 (다익스트라)

rlaxodnd5 4년 전 0

lobo_prix 4년 전 1

rlaxodnd5 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말