10217 KCM Travel - 백준

KCM Travel

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

3 초

256 MB

25033

1179

727

12.127%

문제

각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다.

초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, 다가올 결승 대회를 생각하면 대회 외적인 곳에 마음을 쓰고 싶지 않은 것 또한 사실이었다. 그래서 찬민은 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길을 차선책으로 택하기로 하였다.

각 공항들간 티켓가격과 이동시간이 주어질 때, 찬민이 인천에서 LA로 갈 수 있는 가장 빠른 길을 찾아 찬민의 대회 참가를 도와주자.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. T는 항상 1이다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공항의 수 N (2 ≤ N ≤ 100), 총 지원비용 M (0 ≤ M ≤ 10,000), 티켓정보의 수 K (0 ≤ K ≤ 10,000)가 공백으로 구분되어 주어진다. 이어서 K개의 줄에 걸쳐 각 티켓의 출발공항 u, 도착공항 v (1 ≤ u, v ≤ N, u ≠ v), 비용 c (1 ≤ c ≤ M, 정수), 그리고 소요시간 d (1 ≤ d ≤ 1,000) 가 공백으로 구분되어 주어진다. 인천은 언제나 1번 도시이고, LA는 언제나 N번 도시이다

출력

각 테스트 케이스당 한 줄에 찬민이 LA에 도착하는 데 걸리는 가장 짧은 소요시간을 출력한다.

만약, LA에 도착할 수 없는 경우 "Poor KCM"을 출력한다.

예제 입력 1 복사

1
3 100 3
1 2 1 1
2 3 1 1
1 3 3 30

예제 출력 1 복사

2

예제 입력 2 복사

1
4 10 4
1 2 5 3
2 3 5 4
3 4 1 5
1 3 10 6

예제 출력 2 복사

Poor KCM

출처

Contest > Coder's High > Coder's High 2014 D번

• 데이터를 추가한 사람: doju, pichulia
• 문제의 오타를 찾은 사람: kjho1e3
• 문제를 만든 사람: tae

풀이

첫번째 줄 테스트 케이스 수 T, T는 항상 1, T개의 테스트 케이스 <- 어차피 1개면서 이걸 왜 넣는지 모르겠습니다.

공항의 수 N, 총 지원비용 M 티켓정보의 수 K

K개의 줄

출발공항 u, 도착공항 v 비용 c 소요시간 d

 

인천은 언제나 1번 도시, LA는 언제나 N번 도시

 

일정 비용 내로 이동하는 최단 시간 구하는 문제이기 때문에 다익스트라를 활용

음의 가중치가 없기 때문에 더더욱 다익스트라가 좋음.

코드

package test10217;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static int tc;
	static int N;
	static int M;
	static int K;
	static ArrayList<AirPort>[] list;
	static int[][] money;
	static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);

		tc = sc.nextInt();

		for (int test_case = 0; test_case < tc; test_case++) {
			N = sc.nextInt();
			M = sc.nextInt();
			K = sc.nextInt();
			list = new ArrayList[N + 1];
			money = new int[N + 1][M + 1]; // 앞에는 공항, 뒤에는 비용, 값은 시간

			for (int i = 1; i < N + 1; i++) {
				list[i] = new ArrayList<>();
				Arrays.fill(money[i], Integer.MAX_VALUE);
			}
			


			// 공항 정보
			for (int i = 0; i < K; i++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				int c = sc.nextInt();
				int d = sc.nextInt();

				list[u].add(new AirPort(v, c, d));
			}
			
			for(int i = 0; i < M +1; i++) {
				money[1][i] = 0;
			}

			algorithm();

			if (answer == Integer.MAX_VALUE) { // 도착하지 못했을 때
				sc.write("Poor KCM\n");
			} else {
				sc.write(answer + "\n");
			}

		}

		sc.close();

	}

	static void algorithm() {
		PriorityQueue<AirPort> pq = new PriorityQueue<AirPort>();
		pq.offer(new AirPort(1, 0, 0));//1번 공항은 0원 소비, 0 시간 소요

		while (!pq.isEmpty()) {
			AirPort nowAirPort = pq.poll();
			
			int nowAirPortNumber = nowAirPort.number;
			int nowAirPortCost = nowAirPort.cost;

			if(answer <= money[nowAirPortNumber][nowAirPortCost]) {
				continue;
			}


			for (AirPort air : list[nowAirPortNumber]) {
				int nextNum = air.number;
				int nextCost = nowAirPortCost + air.cost ;
				int nextTime = money[nowAirPortNumber][nowAirPortCost] + air.time;

				// 다음 cost 자체가 기준 금액 넘겨버리면 이거는 사용을 못한다.
				if (nextCost > M) {
					continue;
				}
				
				if(answer <= nextTime) {
					continue;
				}
				
				if(nextNum == N) {
					answer = nextTime;
					continue;
				}

				// 이전에 해당 번호 공항 왔을 때의 시간보다 시간이 커버리면 사용 못함.
				if (money[nextNum][nextCost] <= nextTime) {
					continue;
				}

				if(money[nextNum][nextCost] == Integer.MAX_VALUE) {
					// 다시 pq에 넣어서 반복
					pq.offer(new AirPort(nextNum, nextCost, nextTime));
				}
				money[nextNum][nextCost] = nextTime;
			}
		}
	}

	static class AirPort implements Comparable<AirPort> {
		int number; // 공항 번호
		int cost; // 공항 소요시간
		int time; // 소요 돈

		AirPort(int number, int cost, int time) {
			this.number = number;
			this.cost = cost;
			this.time = time;
		}

		// 정렬 순서
		@Override
		public int compareTo(AirPort o) {
			return this.cost - o.cost;
		}
	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}

		int nextInt() throws Exception {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws Exception {
			return Long.parseLong(nextToken());
		}

		void write(String sb) throws IOException {
			writer.write(sb);
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}