백준 10217 - KCM Travel

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

 

시간제한이 10초라는 점과 어떤 도시로 가는 최소 시간을 구해야 하는 최단경로에 'M원 이하를 사용해야 한다'라는 제약 조건이 붙어있다.

 

인천에서 LA로 가는 최단 경로만 구해야 되므로 여기에 가장 특화된 다익스트라 알고리즘 사용을 최우선적으로 고려할 수 있다.

 

다만, 'M원 이하 사용'의 제약 조건으로 인해 DP가 가미된다는 걸 알 수 있는데 문제는 어떤 것을 메모이제이션 해야 하는가이다.

 

DP 배열의 구성을 생각하기 위해 주어진 정보를 정리하면 출발하는 인천의 번호는 무조건 1이다. LA의 번호는 무조건 N(도시의 개수)이다.

 

시작과 도착이 고정되어 있으므로 다음 1차원 배열을 생각해볼 수 있다.

 

DP[x] == 1에서 x까지의 최단시간

 

그런데 사용되는 금액도 생각해야 하므로 사용된 금액도 고려한 2차원 배열을 만들 수 있다.

 

DP[x][c] == 1에서 x까지 c원을 썼을 때 최단시간

 

점화식을 세우면 DP[x][c] = DP[직전 방문한 도시][직전 도시까지 사용한 금액] + 비행기 시간

 

DP 배열을 구성했으니 다익스트라 알고리즘을 이용하여 최단 시간을 구하면 된다.

 

#include <queue>
#include <tuple>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[101][10001] {};
const string poor("Poor KCM");
const int INF(3000000);

int dijkstra(vector<vector<tuple<int, int, int>>> &adj, int reach, int maximum);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    while (n--)
    {
        memset(dp, -1, sizeof dp);
        dp[1][0] = 0;
        
        int v, limit, e;
        cin >> v >> limit >> e;
        
        // 소요 시간과 소요 금액을 한 객체에 모두 담기 위해 tuple을 이용하였다.
        vector<tuple<int, int, int>> tmp;
        vector<vector<tuple<int, int, int>>> al(v, tmp);
        
        while (e--)
        {
            int start, dest, fee, wait;
            cin >> start >> dest >> fee >> wait;
            al[start - 1].push_back(make_tuple(wait, fee, dest));
        }
        
        int res(dijkstra(al, v, limit));
        
        if (res == -1)
            cout << poor << "\n";
        else
            cout << res << "\n";        
    }
}

int dijkstra(vector<vector<tuple<int, int, int>>> &adj, int reach, int maximum)
{
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
    
    q.push(make_tuple(0, 0, 1));
    
    while (!q.empty())
    {
        int cloc(get<0>(q.top()));
        int cost(get<1>(q.top()));
        int here(get<2>(q.top()));
        q.pop();
        
        
        if (dp[here][cost] < cloc)
            continue;
        
        for (auto item : adj[here - 1])
        {
            int waiting(get<0>(item));
            int saved(get<1>(item));
            int next(get<2>(item));
            
            int nextcost(cost + saved);
            int nextcloc(cloc + waiting);

            // 최대 금액을 넘어버리면 해당 노드를 버린다.
            if (nextcost > maximum)
                continue;
                
            if (dp[next][nextcost] == -1 || dp[next][nextcost] > nextcloc)
            {
                dp[next][nextcost] = nextcloc;
                q.push(make_tuple(nextcloc, nextcost, next));
            }
        }
    }
    
    int last(INF);
    for (int i = 1; i <= maximum; ++i)
    {
        if (dp[reach][i] == -1)
            continue;
        
        if (last > dp[reach][i])
            last = dp[reach][i];
    }
    
    if (last == INF)
        return -1;
    else
        return last;
}