글 읽기 - 이 코드가 틀린 이유를 모르겠습니다(자바)

wbjkwjj 3년 전 0

최단거리의 최대값이 int의 표현범위를 넘어서서 그런가라고 생각하여 가중치의 자료형을 long으로 바꿔보았습니다만

"출력 초과"라는 결과를 받았습니다.

잘못된 부분이 있다면 지적 부탁드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.String;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.lang.Integer;
import java.util.PriorityQueue;

public class Main{

    static class Edge implements Comparable<Edge>{
        /*
        dist[]:Edge(destination from start point, cost to destination(inf if impossible to reach))
        each element of dist[] goes into priority queue
        graph.get(i): Edge(each point j adjacent to point i, weight of edge that j and i makes)
        */
        private int v;
        private int weight;
        public Edge(int vertex_num, int w){
            this.v=vertex_num;
            this.weight=w;
        }
        
        @Override
        public int compareTo(Edge edge){
            return Integer.compare(this.weight,edge.weight);
        }
        
        @Override
        public String toString(){
            return this.weight+"";
        }
    }

  public static void main (String args[]) throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st= new StringTokenizer(br.readLine());
        int V= Integer.parseInt(st.nextToken());
        int E= Integer.parseInt(st.nextToken());
        PriorityQueue<Edge> pq= new PriorityQueue<>();
        boolean[] visited= new boolean[V];
        Edge[] dist= new Edge[V];// distance from starting node
        int from=Integer.parseInt(br.readLine());//start point
        from-=1;
        ArrayList<ArrayList<Edge>> graph= new ArrayList<>();//adjacent list
        for(int i=0;i<V;i++){
            graph.add(new ArrayList<Edge>());
            }
        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 weight= Integer.parseInt(st.nextToken());
            graph.get(start-1).add(new Edge(end-1,weight));
        }
        for(int i=0;i<V;i++){
            if(i==from){
                dist[i]=new Edge(i,0);
            }
            else{
                dist[i]=new Edge(i,Integer.MAX_VALUE);
            }
            pq.add(dist[i]);
            visited[i]=false;
        }
        while(pq.peek()!=null){
            Edge curr=pq.poll();
            
            if(curr.weight>dist[curr.v].weight)
                continue;//Set weight of curr.v is already lighter than weight of current item. There is no need to see further about this item.
            
            
            for(Edge next:graph.get(curr.v)){
                if(!visited[next.v]&&dist[next.v].weight>dist[curr.v].weight+next.weight){
                    dist[next.v].weight=dist[curr.v].weight+next.weight;
                    pq.offer(new Edge(next.v,dist[next.v].weight));
                }
                
            }
            visited[curr.v]=true;
        }
        
        for(Edge edge: dist){
            if(edge.weight!=Integer.MAX_VALUE)
                System.out.println(edge.toString());
            else
                System.out.println("INF");
        }
        
    }
}

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

문제

문제

출처

ICPC

이 코드가 틀린 이유를 모르겠습니다(자바)

wbjkwjj 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말