[Algorithm] 백준 10217 KCM Travel - C++, 다익스트라, DP

10217번: KCM Travel

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

int airport[101][10001];
const int MAX = INT32_MAX;
int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // set test case
    int t;
    cin >> t;
    while (t--){
        // input
        int n, m, k;
        cin >> n >> m >> k;
        vector<pair<int, pair<int, int>>> edges[n+1]; // from -> to, cost, distance
        for(int i = 0; i < k; i++){
            int from, to, c, d;
            cin >> from >> to >> c >> d;
            edges[from].push_back(make_pair(to, make_pair(c, d)));
        }

        // init array
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= m; j++){
                airport[i][j] = MAX;
            }
        }

        // Djikstra
        priority_queue<pair<int, pair<int, int>>> q; // distance, node, cost
        q.push(make_pair(0, make_pair(1, 0)));
        airport[1][0] = 0;

        while (!q.empty()){
            int curPos = q.top().second.first;
            int curDistnace = -q.top().first;
            int curCost = q.top().second.second;
            q.pop();

            if(airport[curPos][curCost] < curDistnace)
                continue;

            for(int i = 0; i < edges[curPos].size(); i++){
                int nextPos = edges[curPos][i].first;
                int nextDistance = edges[curPos][i].second.second + curDistnace;
                int nextCost = edges[curPos][i].second.first + curCost;

                if(nextCost > m)    continue;
                if(airport[nextPos][nextCost] <= nextDistance)  continue;

                airport[nextPos][nextCost] = nextDistance;
                
                for(int j = nextCost + 1; j <= m; j++){
                    if(airport[nextPos][j] <= nextDistance)
                        break;
                    airport[nextPos][j] = nextDistance;
                }

                q.push(make_pair(-nextDistance, make_pair(nextPos, nextCost)));
            }
        }
        
        // find output
        int answer = MAX;
        for(int i = 0; i <= m; i++){
            answer = min(airport[n][i], answer);
        }

        if(answer != MAX)
            cout << answer << '\n';
        else
            cout << "Poor KCM" << '\n';
    }
}

---

 다익스트라 + dp 로 풀이를 해야 합니다. 처음 문제를 풀 때는 다익스트라 단독으로 하니 12% 정도에서 틀렸습니다가 나오게 됩니다.(예제는 맞게 나옴) 그래서 생각해보니 거리는 길지만 요금이 적게 나오는 경우에 대한 대비가 없었으며 이로 인해서 DP 를 섞어서 풀이를 했어야 했습니다.

 위 코드에서 airport 배열로 [공항 번호][까지 오는데 비용] = 거리 를 저장해 위 경우를 대비할 수 있게 했습니다.

 

 추가적으로 queue에 푸쉬를 하기 전 [공항번호][까지 오는데 비용 + 1] 부터 m 까지 돌면서 가격이 더 적은 경우에 수가 있음을 배열에 표기해줘야 문제가 풀리게 됩니다.