글 읽기 - 런타임 에러 or 틀린 케이스 도와주세요! ㅜㅜ

shfksekdrms2 6년 전 0

9%에서 런타임 에러 뜨는데 왜 뜨는지 잘 모르겠어요;;

공간은 2차원으로 정점갯수로 표현했고 INF도 적절한 크기로 설정했는데...

속도도 아무리 늦어도 O(n^2) 이라고 생각하는데... 틀린 부분있으면 알려주세요 감사합니다... ㅜㅜ

import java.util.ArrayList;
import java.util.Scanner;

//1753
public class Main {
	static int maxValue = 2000*2000;
	static int[][] arr;
	static int[] shortPath;
	static ArrayList<Integer> S;
	static ArrayList<Integer> Q;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int K = sc.nextInt();
		int i, j;
		int u,v,w;
		arr = new int[V][V];
		shortPath = new int[V];
		S = new ArrayList<Integer>();
		Q = new ArrayList<Integer>();
		
		for(i=0; i<V; i++){
			shortPath[i] = maxValue;
			Q.add(i+1);
			for(j=0; j<V; j++){
				arr[i][j] = maxValue;
			}
		}
		for(i=0; i<E; i++){
			u=sc.nextInt();
			v=sc.nextInt();
			w=sc.nextInt();
			if(arr[u-1][v-1] != maxValue){
				if(arr[u-1][v-1] > w){
					arr[u-1][v-1] = w;
				}
			}else{
				arr[u-1][v-1] = w;
			}
		}
		shortPath[K-1]=0;
		dijkstra(K);
		for(i=0; i<shortPath.length; i++){
			if(shortPath[i] != maxValue){
				System.out.println(shortPath[i]);
			}else{
				System.out.println("INF");
			}
		}
	}
	
	public static void dijkstra(int k){
		int i;
		for(i=0; i<Q.size(); i++){
			if(k == Q.get(i)){
				Q.remove(i);
				S.add(i+1);
			}
		}
		for(i=0; i<arr.length;i++){
			if(arr[k-1][i] != maxValue){
				if(shortPath[i] == maxValue){
					if(shortPath[k-1]+arr[k-1][i] < maxValue){
						shortPath[i] = shortPath[k-1] + arr[k-1][i];
					}
				}else{
					if(shortPath[i] > shortPath[k-1] + arr[k-1][i]){
						shortPath[i] = shortPath[k-1] + arr[k-1][i];
					}
				}
			}
		}
		int minValueIndex=maxValue;
		int value;
		if(Q.isEmpty() == false){
			for(i=0; i<Q.size(); i++){
				if((value = Q.get(i)) < minValueIndex){
					minValueIndex = value;
					k = minValueIndex;
				}
			}
			dijkstra(k);
		}
	}
}

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

문제

문제

출처

ICPC

런타임 에러 or 틀린 케이스 도와주세요! ㅜㅜ

shfksekdrms2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말