글 읽기 - 런타임에러.. 경로 추적 방식이 틀린건가요??

sksdong1 7년 전 0

런타임 에러가 아무래도 경로 추적하는데서 나는거 같은데

어디가 틀린걸까요?? 1차원 배열에 거리가 경신되면 이전 경로가 바뀌면서 출발점 찾아갈 수 있을거 같은데

문제를 모르겠네용..

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

class Main{
	
	static final int INF = 1000000000;
	static int n,m,s,end;
	static int dist[] = new int[1001];
	static int via[] = new int[1001];
	static Vector<Vector<Edge>> adj = new Vector<Vector<Edge>>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		
		for(int i=0;i<=1000;i++) adj.add(new Vector<Edge>());
		
		for(int i=0;i<m;i++){
			st = new StringTokenizer(br.readLine().trim());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			adj.get(a).add(new Edge(b,c));
		}
		
		st = new StringTokenizer(br.readLine().trim());
		s = Integer.parseInt(st.nextToken());
		end = Integer.parseInt(st.nextToken());

		diik(s);
		
		System.out.println(dist[end]); //최소비용
		
		Vector<Integer> picked = new Vector<Integer>();
		while(end!=s){
			picked.add(end);
			end  = via[end];
		}
		picked.add(s);
		Collections.reverse(picked);
		System.out.println(picked.size());
		for(int i=0;i<picked.size();i++)
			System.out.print(picked.get(i)+" ");
		
	}
	public static void diik(int start){
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		Arrays.fill(dist, INF);
		dist[start]=0;
		q.add(new Edge(start,0));
		
		while(!q.isEmpty()){
			Edge e = q.poll();
			int here = e.u;
			int cost = e.c;
			if(dist[here]<cost) continue;
			for(int i=0;i<adj.get(here).size();i++){
				int there = adj.get(here).get(i).u;
				int nextCost = adj.get(here).get(i).c + dist[here];
				if(dist[there]>nextCost){
					q.add(new Edge(there,nextCost));
					dist[there] = nextCost;
					via[there] = here;
				}
			}
		}
	}
}

class Edge implements Comparable<Edge>{
	int u,c;
	public Edge(int u,int c){
		this.u=u;this.c=c;
	}
	@Override
	public int compareTo(Edge o) {
		return c-o.c;
	}
}

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

문제

문제

출처

ICPC

런타임에러.. 경로 추적 방식이 틀린건가요??

sksdong1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말