백준 10217 - KCM Travel

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 1부터 N까지 가는 경로 중 M이하의 비용을 소모하는 가장 짧은 경로를 찾아내는 것이다.

다른 그래프 문제와 비슷해 보이지만, 비용이 하나 더 추가되었다.

 

문제를 풀기 위해서는 다익스트라를 사용하면 된다.

해당 위치에 도착하는 시간을 기록하며 잘라내면 된다.

하지만, 비용을 신경 써야 한다.

만약, 도착한 비용에 다음으로 진행할 비용을 더했을 때, M보다 크다면 해당 분기는 불가능한 경로이다.

또한, 도착한 위치에 똑같은 비용으로 이미 도착한 적이 있을 때, 시간이 더 걸리는 경우라면 해당 경로도 불가능하다.

즉, 이차원 배열을 통해 도착한 위치와 비용을 기준으로 시간을 기록하면 된다.

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

모든 경로는 1에서 시작한다.

1에서 이동할 수 있는 노드는 2와 3이 있다.

이런 방식으로 다익스트라를 진행하면 된다.

만약, 현재 비용 + 다음 비용이 M을 넘으면 더 이상 진행하지 않는다.

또한, 현재 비용 + 다음 비용에 기록되어 있는 시간이 더 짧다면 마찬가지로 진행하지 않는다.

while (!p.empty())
{
    auto [time, cost, current] = q.front();
    q.pop();

    if (dist[current][cost] < time) continue;

    for (auto [next, c, d] : adj[current])
    {
        if (cost + c > M) continue;
        int totalCost = cost + c;

        if (dist[next][totalCost] > dist[current][cost] + d)
        {
            dist[next][totalCost] = dist[current][cost] + d;
            if (next == N)
            {
                ans = min(ans, dist[next][totalCost]);
                continue;
            }

            q.push({ dist[next][totalCost], totalCost, next});
        }
    }
}

여기서 특이한 점이 있다.

priority_queue가 아니라 queue를 사용한다는 점이다.

해당 문제는 시간제한이 상당히 타이트한 편이다.

따라서, priority_queue를 이용하여 정렬을 하고 조금씩 점진적으로 배열을 업데이트하면 시간초과가 걸린다.

그래서 queue를 이용하여 업데이트를 진행한다.

 queue를 사용해도 문제가 되지 않는 이유는 최초 도착을 구하는 것이 아니며, 메모이제이션을 통해 위치와 비용에 대해 모두 기록하고 있기 때문에 불가능한 경로를 충분히 잘라낼 수 있다. 

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, M, K;
const int MAX = 10'000 * 10'000 + 1;

int Djik(vector<vector<tuple<int, int, int>>>& adj)
{
    //time, cost, node
    queue<tuple<int, int, int>> q;
    vector<vector<int>> dist(N + 1, vector<int>(M+1, MAX));
    int ans = MAX;

    dist[1][0] = 0;
    q.push({ 0, 0, 1 });

    while (!q.empty())
    {
        auto [time, cost, current] = q.front();
        q.pop();

        if (dist[current][cost] < time) continue;

        for (auto [next, c, d] : adj[current])
        {
            if (cost + c > M) continue;
            int totalCost = cost + c;

            if (dist[next][totalCost] > dist[current][cost] + d)
            {
                dist[next][totalCost] = dist[current][cost] + d;
                if (next == N)
                {
                    ans = min(ans, dist[next][totalCost]);
                    continue;
                }

                q.push({ dist[next][totalCost], totalCost, next});
            }
        }
    }

    return ans;
}

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

    int T;
    cin >> T;

    while (T-- > 0)
    {
        cin >> N >> M >> K;

        vector<vector<tuple<int, int, int>>> adj(N+1);

        for (int i = 0; i < K; i++)
        {
            int u, v, c, d;
            cin >> u >> v >> c >> d;

            adj[u].push_back({ v, c, d });
        }

        int ans = Djik(adj);
        if (ans == MAX) cout << "Poor KCM\n";
        else cout << ans;
    }
 
    return 0;
}

---