글 읽기 - 어디가 틀렸는지 모르겠습니다ㅠㅠ

wowbbug 3년 전 0

아무리 이리저리 바꿔봐도 제출 시 답이 틀렸다고 하는데...
코딩이 잘못된건지, 아니면 다른 무언가 반례를 놓친건지...
잘 모르겠습니다ㅠㅠㅠ 가이드 부탁드립니다....

import java.util.*;
import java.io.*;
public class Main {
	
	static class Node implements Comparable<Node>{
		int next;
		long cost;
		int wrap;
		
		Node(int next, long cost, int wrap){
			this.next = next;
			this.cost = cost;
			this.wrap = wrap;
		}

		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return Long.compare(this.cost, o.cost);
		}


	}
	
	static List<List<Node>> li;
	static long[][] weightList;
	static int N, wrap_N;
	static long MAX = Long.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		StringTokenizer str =new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(str.nextToken());
		int line=Integer.parseInt(str.nextToken());
		wrap_N=Integer.parseInt(str.nextToken());
		
		li = new LinkedList<List<Node>>();
		weightList = new long[wrap_N+1][N+1];
		
		
		for(int i=0; i<=N; i++) {
			li.add(new LinkedList<>());
			
		}
		
		for(int w=0; w<=wrap_N; w++) {
			Arrays.fill(weightList[w], MAX);
			weightList[w][1] = 0;
		}
		
		
		for(int l=0; l<line; l++) {
			str =new StringTokenizer(br.readLine());
			
			int a=Integer.parseInt(str.nextToken());
			int b=Integer.parseInt(str.nextToken());
			long c=Integer.parseInt(str.nextToken());
			
			li.get(a).add(new Node(b, c, 0));
			li.get(b).add(new Node(a, c, 0));
		}
		
		
		dij();

		/*if(wrap_N>N-1) {
			System.out.println("0");
		} else {
			System.out.println(weightList[wrap_N][N]);
		}*/
		
	
	}


	private static void dij() {
		// TODO Auto-generated method stub
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(1, 0, 0));
		
		while(!pq.isEmpty()) {
			Node n = pq.poll();
			int n_next = n.next;
			long n_cost = n.cost;
			int n_wrap = n.wrap;
			
			
		//	if(weightList[n_wrap][n_next]<n_cost) continue;
			if(n_next==N) {
				System.out.println(n_cost);
				return;
			}
			
			
			for(Node nn : li.get(n_next)) {
				int nn_next=nn.next;
				long nn_cost=nn.cost;
				int nn_wrap=nn.wrap;
				
			
				
				if(n_wrap<wrap_N && weightList[n_wrap+1][nn_next] > n_cost ) {
			//	if(n_wrap<wrap_N && weightList[n_wrap+1][nn_next] > weightList[n_wrap][n_next] ) {
					//weightList[nn_wrap+1][nn_next] = n_cost;
					// weightList[n_wrap+1][nn_next] = weightList[n_wrap][n_next];
					weightList[n_wrap+1][nn_next] = n_cost;
				//	System.out.println(nn_next+" "+n_cost+" "+(nn_wrap+1));
					pq.add(new Node(nn_next,  n_cost, nn_wrap+1));
					 //pq.add(new Node(nn_next,  weightList[n_wrap+1][nn_next], nn_wrap+1));
				// pq.add(new Node(nn_next, weightList[nn_wrap+1][nn_next], nn_wrap+1));
					
					
				}
				
				if( weightList[n_wrap][nn_next] > n_cost+nn_cost) {
					weightList[n_wrap][nn_next] = n_cost+nn_cost;
					// System.out.println(nn_next+" "+weightList[n_wrap][nn_next]+" "+nn_wrap);
					 pq.add(new Node(nn_next,weightList[n_wrap][nn_next], nn_wrap));
				}
				
				
			}
			
			
			
		}
		
	}
	
	

}

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠습니다ㅠㅠ

wowbbug 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말