백준 : 10217

https://www.acmicpc.net/problem/10217

10217번: KCM Travel

 

문제 접근 방법

제약시간 10초에 많은 TestCase를 테스트하는 문제였다.

처음에는 단방향 노드인데 아무생각없이 양방향노드로 설정해두고 그래서 시간초과해서 틀렸다.

문제를 보면 비용안에서 최단시간을 구하는문젠다. 따라서 digit 배열이 1차원이 아닌 2차원으로 어느비용에서 최단으로 갈수 있는지 선택하면된다.

또한 priorityQueue를 이용해서 제일 N에 먼저도착하는 노드가 제일 빠른시간이되도록 만들어줌으로서 시간을 줄일수가 있다.

package day0308;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class B10217 {
    static final int INF = Integer.MAX_VALUE;
    static int Answer = INF;
    static int T;
    static int N, M, K;
    static int digit[][];
 
    static class VER implements Comparable<VER>{
        int u;
        int c;
        int d;
 
        public VER(int u, int c, int d) {
            super();
            this.u = u;
            this.c = c;
            this.d = d;
        }
 
        @Override
        public int compareTo(VER o) {
            return this.d-o.d;
        }
    }
 
    static PriorityQueue<VER> q;
    static ArrayList<VER> ver[];
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
    
        for (int t = 1; t <= T; t++) {
            Answer = INF;
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            digit = new int[N + 1][M + 1];
            ver = new ArrayList[N + 1];
            for (int n = 1; n <= N; n++) {
                ver[n] = new ArrayList<VER>();
                Arrays.fill(digit[n], INF);
            }
 
            for (int k = 0; k < K; k++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());
 
                ver[u].add(new VER(v, c, d));
//                ver[v].add(new VER(u, c, d));
            }
            q = new PriorityQueue<>();
            digit[1][0] = 0;
            q.add(new VER(1, 0, 0));
 
            while (!q.isEmpty()) {
                VER cur = q.poll();
                if (cur.u == N) {
                    Answer = Math.min(Answer, cur.d);
                    break;
                }
 
                for (VER next : ver[cur.u]) {
                    int sumc = cur.c + next.c;
                    if (sumc > M)
                        continue;
                    int sumd = cur.d + next.d;
                    if (digit[next.u][sumc] > sumd) {
                        digit[next.u][sumc] = sumd;
                        q.add(new VER(next.u, sumc, sumd));
                    }
 
                }
            }
 
            if (Answer == INF) {
                sb.append("Poor KCM\n");
            } else {
                sb.append(Answer+"\n");
            }
 
        }
        System.out.print(sb.toString());
 
    }
 
}