[백준 10217] KCM Travel (C++)

10217번: KCM Travel

다익스트라, 다이나믹 프로그래밍

---

 

[백준 17182] 우주 탐사선 (C++)

위 문제와 비슷한 다익스트라+DP문제였다. (주유소_13308 도 비슷하다)

 

하지만 이번 KCM문제는 최단 시간을 구하는것 뿐만 아니라 이동간의 비용이 추가되어 특정 비용 이내에 있는 최단 시간을 구해야 한다.

그래서 N에 도달했다고 바로 끝내지 않고 N에 도달할 수 있는 모든 비용에 해당하는 시간을 계산한 후 0부터 M까지의 비용중 가장 적게 걸린 시간을 출력하는식으로 답을 도출했다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
struct IF{
    int dest, cost, time;
};
 
int N, M, K;
vector<IF> adj[10001];
int dist[101][10001];
 
void input(){
    for(int i = 0; i < 10001; i++){
        adj[i].clear();
    }
    
    cin >> N >> M >> K;
    int u, v, c, d;
    for(int i = 0; i < K; i++){
        cin >> u >> v >> c >> d;
        adj[u].push_back({v, c, d});
    }
    for(int i = 0; i <= 100; i++){
        for(int j = 0; j < 10001; j++){
            dist[i][j] = INF;
        }
    }
}
 
struct cmp{
    bool operator()(IF &a, IF &b){
        return a.cost > b.cost;
    }
};
 
void solve(){
    priority_queue<IF, vector<IF>, cmp> pq;
    pq.push({1, 0, 0});
    dist[1][0] = 0;
    
    while(!pq.empty()){
        int now = pq.top().dest;
        int now_cost = pq.top().cost;
        int now_time = pq.top().time;
        pq.pop();
        
        if(dist[now][now_cost] < now_time || now_cost > M) continue;
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].dest;
            int next_cost = adj[now][i].cost + now_cost;
            int next_time = adj[now][i].time + now_time;
            
            if(dist[next][next_cost] <= next_time || next_cost > M) continue;
            dist[next][next_cost] = next_time;
            pq.push({next, next_cost, next_time});
            
        }
    }
}
 
int main(){
    int T;
    cin >> T;
    while(T--){
        input();
        solve();
        int res = INF;
        for(int i = 1; i <= M; i++){
            res = min(res, dist[N][i]);
        }
        if(res != INF) cout << res << "\n";
        else cout << "Poor KCM\n";
    }
    
    return 0;
}