글 읽기 - 왜 틀렸는지 모르겠습니다 ㅜㅜ ..

chucky3 6년 전 0

큐를 이용한 다익스트라로 nlogn 시간복잡도 갖도록 작성했고,

메모리 초과 막기 위해 ArrayList[] 로 인접리스트 저장했습니다

런타임 에러는 나지 않는데 틀렸다고 계속 나오는데 정말 모르겠습니다 ㅜㅜ

import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;

public class Main {
	static int V,E,K,u,v,w,INF=11;
	static List<Node>[] adj;
	static int[] dist;
	
	public static void main(String arg[]){
		Scanner sc = new Scanner(System.in);
		V=sc.nextInt();
		E=sc.nextInt();
		K=sc.nextInt();
		
		adj=new ArrayList[V+1];
		dist=new int[V+1];
		
		for(int i=1;i<=V;i++){
			adj[i]=new ArrayList<Node>();
		}
		
		
		for(int i=0;i<E;i++){ //인접 리스트,가중치
			u=sc.nextInt();
			v=sc.nextInt();
			w=sc.nextInt();
			
			adj[u].add(new Node(v,w));
		}
		
		for(int i=1;i<=V;i++){ //dist 초기화
			dist[i]=INF;
		}
		
		PriorityQueue<Node> q = new PriorityQueue<Node>(); //우선순위 큐
		dist[K]=0; //시작점
		q.offer(new Node(K,dist[K])); //q insert
		
		while(!q.isEmpty()){
			K=q.peek().index;
			q.poll();
			
			for(int j=0;j<adj[K].size();j++){
				int index = adj[K].get(j).index;
				if(dist[index]>dist[K]+adj[K].get(j).distance){
					dist[index]=dist[K]+adj[K].get(j).distance;
					q.offer(new Node(index,dist[index]));
				}
			}
		}
		
		for(int i=1;i<=V;i++){//출력
			System.out.println(dist[i]!=INF?dist[i]:"INF");
		}
	}
}
class Node implements Comparable<Node>{
	int index;
	int distance;
	
	public Node(int index,int distance){
		this.index=index;
		this.distance=distance;
	}
	
	public int compareTo(Node n){
		return distance <= n.distance ? -1 : 1;
	}
}

lll4592 6년 전 1

가중치의 합이 10 이하가 아닙니다. INF 를 더 큰수로 정하세요.

chucky3 6년 전 0

감사합니다! ㅎㅎ

dsemnai 5달 전 0

아 맞다 이것도..

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다 ㅜㅜ ..

chucky3 6년 전 0

lll4592 6년 전 1

chucky3 6년 전 0

dsemnai 5달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말