글 읽기 - 1753번 시간초과 질문입니다.

alalssg 5년 전 0

안녕하세요

정말 많은 생각을 하면서 고민하고 있지만 지속적으로 발생하는 시간초과에 어찌할 방도를 모르겠어서 질문을 올립니다.

Node라는 클래스에 정점 번호와 간선의 가중치 값을 저장하고

PriorityQueue로 가중치가 작은 정점부터 꺼내서 최소 거리를 구하고자 했습니다.

하지만 제가 어느 부분에서 시간을 잡아 먹고 있는지 아무리 고민을 해보아도 보이질 않습니다.

제가 어느 부분을 놓치고 있는지 시야를 넓혀주실수 있을까요?

감사합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static ArrayList<ArrayList<Node>> connNodeList;
	public static int[] distance;
	public static 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 nodeCnt = Integer.parseInt(st.nextToken());
		int lineCnt = Integer.parseInt(st.nextToken());
		
		connNodeList = new ArrayList<>();
		distance = new int[nodeCnt+1];
		
		for(int i=0; i <= nodeCnt; i++) {
			distance[i] = INF;
			connNodeList.add(new ArrayList<Node>());
		}
		
		int startNode = Integer.parseInt(br.readLine());
		
		distance[startNode] = 0;
		
		for(int i=0; i < lineCnt; i++) {
			st = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			
			connNodeList.get(num1).add(new Node(num2, dist));
		}
		
		dijkstra(startNode);
		
		for(int i = 1; i <= nodeCnt; i++) {
			bw.write((distance[i] == INF?"INF":distance[i])+"\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static void dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		pq.offer(new Node(start, 0));
		while(!pq.isEmpty()) {
			int num = pq.peek().num;
			int dist = pq.peek().distance;
			pq.poll();
			
			if(dist > distance[num]) continue;
			
			for(Node nextNode:connNodeList.get(num)) {
				int nextNum = nextNode.num;
				int nextDist = nextNode.distance + distance[num];
				
				if(nextDist < distance[nextNum]) {
					distance[nextNum] = nextDist;
					pq.offer(new Node(nextNum, nextDist));
				}
			}
		}
	}
}

class Node implements Comparable<Node>{
	int num;
	int distance;
	
	public Node(int num, int distance) {
		this.num = num;
		this.distance = distance;
	}
	@Override
	public int compareTo(Node target) {
		return(this.num<target.num) ? -1:1;
	}
}

djm03178 5년 전 1

"PriorityQueue로 가중치가 작은 정점부터 꺼내서 최소 거리를 구하고자 했습니다."

priority queue가 어느 원소를 먼저 꺼내야 할지는 87번째 줄의 compareTo가 결정해줍니다. 그런데, 과연 적절한 일을 하고 있을까요?

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

문제

문제

출처

ICPC

1753번 시간초과 질문입니다.

alalssg 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말