글 읽기 - 시간초과_도와주세요ㅠ

ichigo15 6년 전 0

처음에는 2차원 배열로 해결하다가 런타임에러가 떠서
해쉬맵으로 바꿨습니다.
왜 시간초과가 뜨는지 모르겠습니다.

도와주세요 ㅠ

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;


public class Dijkstra {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int numOfNode = sc.nextInt();
		int numOfEdge = sc.nextInt();
		int startNode = sc.nextInt();
		int[] dist = new int[numOfNode+1];
		boolean[] visit = new boolean[numOfNode+1];
		HashMap<Integer, HashMap<Integer, Integer>> adMap = new HashMap<Integer,HashMap<Integer, Integer>>();
		//키값이 시작노드, 두번째 키값이 도착노드, 벨류가 엣지 가중치
		ArrayList<Integer> arriveNodes  = new ArrayList<Integer>();
		
		for(int i =1; i <= numOfEdge; i++){
			int u = sc.nextInt();
			int v = sc.nextInt();
			int val = sc.nextInt();
			if(adMap.get(u) == null) {
				adMap.put(u, new HashMap<Integer,Integer>());
			}
			if(adMap.get(u).get(v) == null) {
				adMap.get(u).put(v, val); 
			} else{
				if(adMap.get(u).get(v) > val) adMap.get(u).put(v, val);
			}
			arriveNodes.add(v);
		}
		for(int i = 1; i <= numOfNode; i++){
			dist[i] = -1;
			//for(int j = 1; j <= numOfNode; j++) System.out.print(adMap.get(i).get(j));
			//System.out.println();
		}
		dist[startNode] = 0;
		PriorityQueue<Integer> nodeStack = new PriorityQueue<Integer>();
		while(true){
			if(!nodeStack.isEmpty()){
				startNode = nodeStack.poll();
			}
			
			for(int i : arriveNodes){
				if(adMap.get(startNode).get(i) != null){
					if(dist[i] == -1){
						dist[i] = dist[startNode] + adMap.get(startNode).get(i);
					}
					else{
						if(dist[i] > dist[startNode] + adMap.get(startNode).get(i)){
							dist[i] = dist[startNode] + adMap.get(startNode).get(i);
						}
					}
					if(visit[startNode] == false){
						nodeStack.add(i);
						visit[i] = true;
					}
				}
			}
			
			//for(int j = 1; j <= numOfNode; j++) System.out.print(dist[j]);
			//System.out.println();
			
			if(nodeStack.isEmpty()){
				break;
			}
		}
		for(int j = 1; j <= numOfNode; j++) {
			if(dist[j] == -1) System.out.println("INF");
			else System.out.println(dist[j]);
		}
	}

}

bupjae 6년 전 1

Java Scanner 클래스는 입력 속도가 *매우* 느린 것으로 악명이 높습니다.

이 정도 규모의 데이터를 입력받을 때는 BufferedReader 를 추천합니다.

ichigo15 6년 전 0

답변 감사합니다!

하지만 BufferedReader로 수정해 봤으나 다시 시간초과가 뜹니다 ㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;


public class Dijkstra {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] input;
		input = in.readLine().split(" ");
		int numOfNode = Integer.parseInt(input[0]);
		int numOfEdge = Integer.parseInt(input[1]);
		int startNode = Integer.parseInt(in.readLine());;
		int[] dist = new int[numOfNode+1];
		boolean[] visit = new boolean[numOfNode+1];
		HashMap<Integer, HashMap<Integer, Integer>> adMap = new HashMap<Integer,HashMap<Integer, Integer>>();
		//키값이 시작노드, 두번째 키값이 도착노드, 벨류가 엣지 가중치
		ArrayList<Integer> arriveNodes  = new ArrayList<Integer>();
		
		for(int i =1; i <= numOfEdge; i++){
			input = in.readLine().split(" ");
			int u = Integer.parseInt(input[0]);
			int v = Integer.parseInt(input[1]);
			int val = Integer.parseInt(input[2]);
			if(adMap.get(u) == null) {
				adMap.put(u, new HashMap<Integer,Integer>());
			}
			if(adMap.get(u).get(v) == null) {
				adMap.get(u).put(v, val); 
			} else{
				if(adMap.get(u).get(v) > val) adMap.get(u).put(v, val);
			}
			arriveNodes.add(v);
		}
		for(int i = 1; i <= numOfNode; i++){
			dist[i] = -1;
			//for(int j = 1; j <= numOfNode; j++) System.out.print(adMap.get(i).get(j));
			//System.out.println();
		}
		dist[startNode] = 0;
		PriorityQueue<Integer> nodeStack = new PriorityQueue<Integer>();
		while(true){
			if(!nodeStack.isEmpty()){
				startNode = nodeStack.poll();
			}
			
			for(int i : arriveNodes){
				if(adMap.get(startNode).get(i) != null){
					if(dist[i] == -1){
						dist[i] = dist[startNode] + adMap.get(startNode).get(i);
					}
					else{
						if(dist[i] > dist[startNode] + adMap.get(startNode).get(i)){
							dist[i] = dist[startNode] + adMap.get(startNode).get(i);
						}
					}
					if(visit[startNode] == false){
						nodeStack.add(i);
						visit[i] = true;
					}
				}
			}
			
			//for(int j = 1; j <= numOfNode; j++) System.out.print(dist[j]);
			//System.out.println();
			
			if(nodeStack.isEmpty()){
				break;
			}
		}
		for(int j = 1; j <= numOfNode; j++) {
			if(dist[j] == -1) System.out.println("INF");
			else System.out.println(dist[j]);
		}
	}

}

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

문제

문제

출처

ICPC

시간초과_도와주세요ㅠ

ichigo15 6년 전 0

bupjae 6년 전 1

ichigo15 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말