글 읽기 - 최소비용 구하기 2 틀린 이유를 모르겠습니다

barcelonamessi 7년 전 0

다익스트라로 시작점부터 최소비용의 거리까지를 구하고

업데이트 할때마다 parent 배열로 참조하는 parent를 바꿔주고

parent배열이 -1일때까지 경로를 찾아가서

출력하는데 어디서 잘못됬는지모르겠어요

30%정도까지 가다가 갑자기 WA뜨네요 ㅜㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Vector;

public class Main {
	static class Vertex{
		int v;
		int D;
		Vertex(){}
		Vertex(int v, int D){
			this.v=v;
			this.D=D;
		}
	}
	static class Edge{
		int from;
		int to;
		int weight;
		Edge(){}
		Edge(int from, int to, int weight){
			this.from=from;
			this.to=to;
			this.weight=weight;
		}
	}
	static class Comp implements Comparator<Vertex>{
		public int compare(Vertex a, Vertex b){
			if(a.D<b.D)
				return -1;
			else if(a.D>b.D)
				return 1;
			else
				return 0;
			
		}
		
	}

	public static void main(String[] args)throws IOException {
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token=new StringTokenizer(in.readLine());
		int N=Integer.parseInt(token.nextToken());

		Vector<Vector<Edge>> edge=new Vector<Vector<Edge>>();
		
		int D[]=new int[N+1];
		int parent[]=new int[N+1];
		int visit[]=new int[N+1];
		for(int i=0; i<=N; i++){
			edge.add(new Vector<Edge>());
			D[i]=Integer.MAX_VALUE;
			parent[i]=-1;
		}
			
		token=new StringTokenizer(in.readLine());
		int M=Integer.parseInt(token.nextToken());
		PriorityQueue<Vertex> pq=new PriorityQueue(M, new Comp());
		for(int i=0; i<M; i++){
			token=new StringTokenizer(in.readLine());
			int from=Integer.parseInt(token.nextToken());
			int to=Integer.parseInt(token.nextToken());
			int weight=Integer.parseInt(token.nextToken());
			edge.get(from).add(new Edge(from, to, weight));
			
		}
		
		token=new StringTokenizer(in.readLine());
		int from=Integer.parseInt(token.nextToken());
		int to=Integer.parseInt(token.nextToken());
		D[from]=0;
		pq.add(new Vertex(from, 0));
		
		int count=0;
		while(!pq.isEmpty()){
			
			Vertex cur=pq.peek();
			pq.remove();
			if(D[cur.v]<cur.D)
				continue;
			
			
			for(int i=0; i<edge.get(cur.v).size(); i++){
				Edge next_v=edge.get(cur.v).get(i);
				int next=next_v.to;
				int next_D=next_v.weight;
				if(D[next]>D[cur.v]+next_D){
					parent[next]=cur.v;
					D[next]=D[cur.v]+next_D;
					pq.add(new Vertex(next, D[next]));
				}
				
			}
		}
		
			System.out.println(D[to]);
		Vector<Integer> v=new Vector<Integer>();
		v.add(to);
		while(parent[to]!=-1){
			to=parent[to];
			v.add(to);
			
		}
		Collections.reverse(v);
		System.out.println(v.size());
		for(int i=0; i<v.size(); i++){
			System.out.print(v.get(i) + " ");
		}
		
		
	}

}

pichulia 7년 전 3

데이터중에 줄 단위로 되있지 않은 데이터가 존재하는 것 같습니다.

입력받을 때 지금처럼 줄 단위로 데이터를 읽고 그것을 분석한게 아니라,

java.util.Scanner 의 nextInt(); 를 이용해서 읽었더니 맞았습니다.

barcelonamessi 7년 전 0

@pichulia 와 정말 감사합니다 ㅜㅜ 저의 구세주이십니다

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

문제

문제

출처

ICPC

최소비용 구하기 2 틀린 이유를 모르겠습니다

barcelonamessi 7년 전 0

pichulia 7년 전 3

barcelonamessi 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말