KCM Travel

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
10 초	256 MB	21759	4834	2300	17.114%

문제

각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 

구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 

최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다.

초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 

인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만,

다가올 결승 대회를 생각하면 대회 외적인 곳에 마음을 쓰고 싶지 않은 것 또한 사실이었다. 

그래서 찬민은 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길을 차선책으로 택하기로 하였다.

각 공항들간 티켓가격과 이동시간이 주어질 때,

찬민이 인천에서 LA로 갈 수 있는 가장 빠른 길을 찾아 찬민의 대회 참가를 도와주자.

입력

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

그 다음에는 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

2
3 100 3
1 2 1 1
2 3 1 1
1 3 3 30
4 10 4
1 2 5 3
2 3 5 4
3 4 1 5
1 3 10 6

예제 출력 1

2
Poor KCM

출처

Contest > Coder’s High > Coder‘s High 2014 D번

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

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 데이크스트라

---

해결 방법

백준 1162번 (도로포장, C++, Dijkstra) / 추가 반례 [BAEKJOON]

1162번 도로포장 문제와 유사한 방법으로 해결하였다.

통과된 코드 (재채점 이후 시간초과)

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

priority_queue<tuple<long long int, int, int>> myPQ;

long long int disArr[101][10001];

constexpr long long int INF = INT64_MAX;

int T, N, M, K, U, V, C, D, cnt;

long long int Dijstra()
{
    cin >> N >> M >> K;

    // 다익스트라 배열 초기화
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= M; j++)
            disArr[i][j] = INF;

    vector<tuple<int, int, int>> graph[10000];

    for (int i = 0; i < K; i++) {
        cin >> U >> V >> C >> D;
        graph[U].push_back(make_tuple(V, C, D));
    }

    // 우선순위 큐에 삽입.
    myPQ.push({ 0, 1, 0 }); // <거리 , 노드 인덱스 , 비용>

    disArr[1][0] = 0;

    while (!myPQ.empty()) {
        // -를 붙이는 이유는 우선순위 큐를 이용하여 정렬하기 위함이다.
        // (최소힙으로 구현)
        long long int nCost = -get<0>(myPQ.top()); // 현재 최단 거리

        int now = get<1>(myPQ.top()); // 현재 노드

        int money = get<2>(myPQ.top()); // 비용 

        myPQ.pop();
        // 이미 담겨 있는 것보다 거리가 크면 넘어간다.
        if (disArr[now][money] < nCost) continue;
        // 해당 노드에서 연결된 모든 경로를 확인
        for (int i = 0; i < graph[now].size(); i++) {

            // 비용의 범위가 초과된다면 continue
            if (money + get<1>(graph[now][i]) > M) continue;

            // disSum = 임시 노드 + 현재 노드에서 i로가는 비용
            long long int disSum = nCost + get<2>(graph[now][i]);

            // 비용이 작다면 최단경로 테이블 값을 갱신.
            if (disSum < disArr[get<0>(graph[now][i])][money + get<1>(graph[now][i])]) {
                // 임시 노드 업데이트
                disArr[get<0>(graph[now][i])][money + get<1>(graph[now][i])] = disSum;
                // 우선순위 큐에 (거리, 노드 인덱스, 비용) 푸시
                myPQ.push({ -disSum, get<0>(graph[now][i]), money + get<1>(graph[now][i]) });

            }
        }
    }

    long long int result = INF;

    for (int i = 0; i <= M; i++) {
       result = min(disArr[N][i], result);
    }

    return result;
}


int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
    cin.tie(NULL);
    std::cout.tie(NULL);

    cin >> T;

    while (T-- > 0) {
        long long int result = Dijstra();
        if (result == INF) cout << "Poor KCM\n";
        else cout << result << "\n";
    }

    return 0;
}

재채점 이후

deque을 이용하여 해결

#include <iostream>
#include <vector>
#include <deque>
#include <cstring>
#define INF 987654321

using namespace std;

struct Info {
    int node;  // 도착 공항
    int cost;  // 티켓 비용
    int time;  // 소요 시간
};

int n, m, k;
vector<vector<Info>> edges;
int dp[101][10001];  // dp[i][j]: i번 공항에 j 비용으로 도착했을 때 최소 소요 시간

void solve() {
    // 공항의 연결 정보 및 dp 배열 초기화
    edges.clear();
    edges.resize(n + 1);

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = INF;
        }
    }

    // 티켓 정보 입력
    for (int i = 0; i < k; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        edges[u].push_back({ v, c, d });
    }

    // deque를 사용한 BFS 기반 탐색 (비용과 시간을 함께 고려)
    deque<pair<int, pair<int, int>>> dq;  // {소요 시간, {공항, 비용}}
    dq.push_back({ 0, {1, 0} });  // 시작점: 1번 공항, 비용 0, 소요 시간 0
    dp[1][0] = 0;  // 1번 공항, 비용 0에서 시작

    while (!dq.empty()) {
        int time = dq.front().first;
        int here = dq.front().second.first;
        int cost = dq.front().second.second;
        dq.pop_front();

        // 이미 더 빠른 경로가 있는 경우 스킵
        if (dp[here][cost] < time) continue;

        // 현재 공항에서 갈 수 있는 다음 공항 탐색
        for (auto& next_info : edges[here]) {
            int next = next_info.node;
            int next_time = time + next_info.time;
            int next_cost = cost + next_info.cost;

            // 비용이 초과하면 무시
            if (next_cost > m) continue;

            // 다음 공항에 대한 비용-시간 정보가 더 최적이면 갱신
            if (next_time < dp[next][next_cost]) {
                dp[next][next_cost] = next_time;
                // deque에 삽입할 때, 비용이 더 낮은 경로를 우선으로 처리
                if (!dq.empty() && dq.front().first > next_time) {
                    dq.push_front({ next_time, {next, next_cost} });
                }
                else {
                    dq.push_back({ next_time, {next, next_cost} });
                }
            }
        }
    }

    int answer = INF;

    // 목적지 공항 n에 비용 m 이하로 도착하는 최소 소요 시간 탐색
    for (int i = 0; i <= m; i++) {
        answer = min(answer, dp[n][i]);
    }

    // 결과 출력: 도착할 수 없으면 "Poor KCM", 그렇지 않으면 최소 소요 시간 출력
    if (answer == INF) cout << "Poor KCM" << endl;
    else cout << answer << endl;
}

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;  // 테스트 케이스 입력
    while (t--) {
        cin >> n >> m >> k;  // 공항 수, 최대 지원 비용, 티켓 정보 수 입력
        solve();
    }

    return 0;
}