글 읽기 - 1753번 다익스트라... 시간초과 뜨는데 어디서 줄여야하나요

ijd0114 5년 전 0

자바만 이런가요..? 다익스트라 알고리즘을 구현했는데 제가 구현잘못한거가요... 자꾸 시간초과가 뜹니다 72퍼정도에서요..

도대체 뭐가 문제인지 모르겠습니다.. ㅠ... 그렇다고 visited 선언해서 풀면 또.. 틀렷따고 나오고..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Graph implements Comparable<Graph>{
    int node;   //정점
    int cost;   //가중치
    
    public Graph(int node, int cost){
        this.node = node;
        this.cost = cost;
    }
    
    @Override
	public int compareTo(Graph obj) {
	    
	    if(this.cost < obj.cost)        return -1;
	    else                            return 1;
	    
	}
}


public class Main {
    static List<Graph>[] graphArr ;
    static int[] cost;
    static int INF = 2147483647;
	public static void  main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));//선언
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		PriorityQueue<Graph> pq = new PriorityQueue<Graph>();
		cost = new int[Integer.parseInt(st.nextToken())+1];
		graphArr =  new ArrayList[cost.length];
		 
		Arrays.fill(cost,INF);
		
	    int	edge = Integer.parseInt(st.nextToken());    //간선수
	    int start = Integer.parseInt(br.readLine());    //시작점
	    for(int i=0; i<graphArr.length;i++)
	        graphArr[i]= new ArrayList<Graph>();
	    
	    
        //그래프 정보 
	    for(int i=0; i<edge; i++){
	        st = new StringTokenizer(br.readLine()," ");
	        int u,v,w;
	        u = Integer.parseInt(st.nextToken());   //부모
	        v = Integer.parseInt(st.nextToken());   //정점
	        w = Integer.parseInt(st.nextToken());   //가중치
	        graphArr[u].add(new Graph(v,w));
	        
	    }
	    cost[start] = 0;    //시작점은 0
	    pq.offer(new Graph(start,0));
	    graphArr[start].add(new Graph(start,0));
	
	    /*경로 업데이트*/ 
	    while(!pq.isEmpty()){
	       Graph parent = pq.poll();
	       
	        if(graphArr[parent.node] != null){
	            for(int i=0; i<graphArr[parent.node].size();i++){
	                Graph child = graphArr[parent.node].get(i);   
	                if(cost[child.node] > cost[parent.node]+ child.cost){
	                    
	                    cost[child.node] =cost[parent.node]+ child.cost;
	                    pq.offer(child);
	                } 
	            }
	                
	       }
	    }
	    
	    	    
	    
	    for(int i=1; i<cost.length;i++)
	    	bw.write((cost[i]==INF)?"INF\n":cost[i]+"\n");//출력
	    
	    bw.flush();//남아있는 데이터를 모두 출력시킴
	    bw.close();//스트림을 닫음
	}
}

ijd0114 5년 전 2

자체 해결했습니다.

74번줄에서 pq.offer(child); 가 아니고 pq.offer(new Graph(child.node, cost[child.node] )); 이네요... ㅎ...

zzz8838 1년 전 0

와..감사합니다. 한 시간동안 헤매다가 덕분에 저도 찾았네요.

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

문제

문제

출처

ICPC

1753번 다익스트라... 시간초과 뜨는데 어디서 줄여야하나요

ijd0114 5년 전 0

ijd0114 5년 전 2

zzz8838 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말