글 읽기 - java 메모리초과 질문

ambl2357 4년 전 0

어느부분에서 메모리 초과가 뜨는 걸까요 ? ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	static int V,E;
	static int K;
	static int[] dist = new int[501];
	static List<Edge>[] edges = new List[501]; 
	static final int MAX_COST = 20001;
	static boolean[] visited = new boolean[20001];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		K =1;
		
		for(int i = 1; i <= V; i++) {
			dist[i] = MAX_COST;
			edges[i] = new ArrayList<>();
		}
		int a,b,c;
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			
			edges[a].add(new Edge(b,c));
		}
		
		PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
			@Override
			public int compare(Edge e1, Edge e2) {
				return e1.cost - e2.cost;
			}
		});
		dist[K] = 0;
		pq.add(new Edge(K,0));
		
		while(!pq.isEmpty()) {
			Edge tmp = pq.poll();
			int src = tmp.dst;
			if(visited[src]) continue;
			visited[src] = true;
			for(int i = 0; i < edges[src].size(); i++) {
				Edge e = edges[src].get(i);
				if(dist[e.dst] > tmp.cost + e.cost) {
					dist[e.dst] = tmp.cost+e.cost;
					pq.offer(new Edge(e.dst, dist[e.dst]));
				}
			}
		}
		pq.add(new Edge(K,0));
		boolean chk = false;
		while(!pq.isEmpty()) {
			
			Edge tmp = pq.poll();
			int src = tmp.dst;
			
			visited[src] = true;
			for(int i = 0; i < edges[src].size(); i++) {
				Edge e = edges[src].get(i);
				if(dist[e.dst] > tmp.cost + e.cost) {
					chk = true;
					break;		
				}
				else 
					pq.offer(new Edge(e.dst, dist[e.dst]));
			}
		}
		
		if(chk) System.out.println("-1");
		else {
			for(int i = 2; i <=V ; i++) {
				if(dist[i] == MAX_COST) System.out.println("-1");
				else System.out.println(dist[i]);
			}
		}	
		
	}
	
	static class Edge{
		int dst;
		int cost;
		Edge(int d, int c){
			dst = d;
			cost = c;
		}
	}
}

lovinix 4년 전 1

아마 터진다면 66~81줄 사이에서 무한루프때문에 터질거같습니다.

74줄에서 dist[e.dst] == tmp.cost + e.cost 인 경우 pq에 계속 edge를 넣는데 여기서 무한루프를 도니까 시간초과 이전에

new Edge() 때문에 메모리가 먼저 터져버리는거같네요

그런데 벨만포드를 우선순위큐로 구현할 수 있나요? 66~81 줄의 해당 구간을 visit[src]==true 인 경우 continue하더라도 음의 사이클이 있는 예제2번을 제대로 통과할거같지 않아보입니다.

ambl2357 4년 전 0

감사합니다~! 남은 수업더 열심히 들으십시연~!

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

문제

문제

출처

ICPC

java 메모리초과 질문

ambl2357 4년 전 0

lovinix 4년 전 1

ambl2357 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말