글 읽기 - 도로포장. 테스트케이스 맞음. 계속 틀리다고나와요..ㅜㅜ

vastnow 2년 전 0

테스트 케이스는 추가로 올려주신 분들것도 다 맞았는데요..

제출하면 틀리다고 나옵니다.

도움을 구할 수 있을까요?

// 백준 > 도로포장 1162
// 도로포장하면 비용이 0이 됨. 비용이 가변적임
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int N, M, K;
	static ArrayList<Doro>[] arrList;
	static long[][] cost; // 포장을 할 때와 하지 않을 때에 따라 cost가 달라지므로 [][]로 선언
	
	static StringTokenizer st;
	public static void main(String[] args) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
	
		
		arrList = new ArrayList[N+1];
		cost = new long[K+1][N+1]; // 포장가능 개수
		
		for(int i=1; i <= N; i++) {
			arrList[i] = new ArrayList<>();
		}
		
		
		
		for(int i=0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from, to, cost;
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			cost = Integer.parseInt(st.nextToken());
			
			arrList[from].add(new Doro(to, cost, K));
			arrList[to].add(new Doro(from, cost, K));
		}
		
		
/*		long ans = Long.MAX_VALUE;
		for(int i=0; i <= K; i++) {
			ans = Math.min(ans, cost[i][N]);
			
		}*/
		System.out.print(dijkstra(1));

	}
	public static void init() {
		for(int i=0; i <= K; i ++) {
			Arrays.fill(cost[i], Integer.MAX_VALUE);
		}
	}
	
	public static long dijkstra(int start) {
		long ans = 0;
		init();
		PriorityQueue<Doro> queue = new PriorityQueue<>();
		cost[K][start] = 0;
		queue.add(new Doro(start, 0, K));
		
		while(!queue.isEmpty()) {
			Doro now = queue.poll();
			
			if(now.dest == N) return now.cost;
			if(cost[now.p][now.dest] < now.cost) continue;

			for(Doro next : arrList[now.dest]) {
				// 도로포장 하지 않을 때
				if(cost[now.p][next.dest] > now.cost + next.cost) {
					cost[now.p][next.dest] = now.cost + next.cost;
					queue.add(new Doro(next.dest, cost[now.p][next.dest], now.p));
				}
				
				// 도로포장 할 때
				if(now.p > 0 && cost[now.p - 1][next.dest] > now.cost + 0) {
					cost[now.p - 1][next.dest] = now.cost + 0;
					queue.add(new Doro(next.dest, cost[now.p - 1][next.dest], now.p - 1));
				}
			}
					
		}
		return ans;
	}

}



class Doro implements Comparable<Doro>{
	int dest;
	long cost;
	int p; // 도로포장 개수 
	Doro(int dest, long cost, int p) {
		this.dest = dest;
		this.cost = cost;
		this.p = p;
	}
	@Override
	public int compareTo(Doro o) {
		// TODO Auto-generated method stub
		return Long.compare(this.cost, o.cost);
	}
}

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

문제

문제

출처

ICPC

도로포장. 테스트케이스 맞음. 계속 틀리다고나와요..ㅜㅜ

vastnow 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말