10217번 KCM Travel

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

java vector 우선순위 큐 Pair pair class 자바 

Java 복습할겸 다시 풀어봤다.

import java.io.*;
import java.util.*;
 
public class Main {
    static int n, m, k;
    static int[][] dist;
    static PriorityQueue<Pair> pq;
    static Vector<Vector<info>> V;
    static BufferedReader br;
    static BufferedWriter bw;
    
    static int dijstra() throws IOException
    {
        pq = new PriorityQueue<Pair>();
        // 현재 총 소모 시간, 현재 위치, 현재까지 사용한 돈(비용)
        pq.add(new Pair(0, 1, 0));
                
        dist = new int[n + 1][10001]; // [현재 위치][현재까지 사용한 돈(비용)]
        for(int i=1; i<=n; i++) {
            Arrays.fill(dist[i], 100000000);
        }
        
        dist[1][0] = 0;
        
 
        while(!pq.isEmpty()) {
            int total_time = pq.peek().first;
            int here = pq.peek().second;
            int used_money = pq.peek().third;
                
            pq.remove();
            
            if(dist[here][used_money] < total_time) {
                continue;
            }
            
            for(info next : V.get(here)) {
                int sum = used_money + next.money;                
                if(sum <= m && dist[next.end][sum] > dist[here][used_money] + next.time) {                        
                    dist[next.end][sum] = dist[here][used_money] + next.time;                
                    pq.add(new Pair(dist[next.end][sum], next.end, sum));
                }
            }
        }
        
        int ret = 100000000;
 
        for(int i=1; i<=m; i++) {
            if(dist[n][i] != 100000000) {
                ret = Math.min(ret, dist[n][i]);
            }
        }
        
        return ret;
    }
    
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int t;
        t = Integer.parseInt(br.readLine());
        
        for(int tc=0; tc<t; tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            
            int u, v, c, d;
            
            V = new Vector<Vector<info>>();
 
            for(int i=0; i<n+1; i++) {
                Vector<info> vt = new Vector<info>();
                V.add(vt);
            }
            
            for(int i=0; i<k; i++) {
                st = new StringTokenizer(br.readLine());
                u = Integer.parseInt(st.nextToken());
                v = Integer.parseInt(st.nextToken());
                c = Integer.parseInt(st.nextToken());
                d = Integer.parseInt(st.nextToken());
                
                V.get(u).add(new info(v, c, d));
            }
            
            int g = dijstra();
            
            if(g==100000000) {
                bw.write(String.valueOf("Poor KCM") + "\n");
            }
            else {
                bw.write(String.valueOf(g) + "\n");
            }    
        }
        
        bw.flush();
        bw.close();
    }
}
 
class Pair implements Comparable<Pair> {
    int first, second, third;
    
    Pair(int f, int s, int t) {
        this.first = f;
        this.second = s;
        this.third = t;
    }
    
    public int compareTo(Pair p) {
        if(this.first < p.first) {
            return -1; // 오름차순
        }
        else if(this.first == p.first) {
            if(this.second < p.second) {
                return -1;
            }
            else if(this.second == p.second) {
                if(this.third < p.third) {
                    return -1;
                }
            }
        }
        
        return 1; 
        // 이미 this.first가 더 큰 것이 됐으므로, 1로 해준다.
        // -1로 하면 결과가 이상하게 출력됨.
    }
}
 
class info {
    int end, money, time;
    info(int a, int b, int c) {
        this.end = a;
        this.money = b;
        this.time = c;
    }
}