10217 - KCM Travel

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

주어진 비용으로 갈 수 있는 1번~모든 노드의 최단 거리를 구한다.

구하는 과정에서 아래와 같이 정보를 저장한다.

dp(i, k) = i번 노드까지 k의 비용으로 갔을 때의 최소 시간

주어진 비용 내에서 N번 노드까지 간 최소 시간을 구하면 된다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

struct node {
    int pos, cost, time;
    bool operator < (const node& p) const {
        if(this->time == p.time) return this->cost > p.cost;
        return this->time > p.time;
    }
};

int dp[101][10001]; // i번 노드까지 k의 비용으로 갔을 때의 최소 시간
vector<node> adj[101];
priority_queue<node> q;

int dijkstra(int nodes, int money){
    for(int i=0; i<nodes; ++i){
        for(int j=0; j<=money; ++j) dp[i][j] = INF;
    }
    
    q = {};
    q.push({0, 0, 0});
    dp[0][0] = 0;
    
    while(!q.empty()){
        node top = q.top();
        q.pop();
        
        int cost  = top.cost;
        int dtime = top.time;
        int pos   = top.pos;
        if(pos == nodes-1) break;
        
        if(dp[pos][cost] < dtime) continue;
        dp[pos][cost] = dtime;
        
        for(int i=0; i<adj[pos].size(); ++i){
            node& next = adj[pos][i];
            
            if(cost + next.cost > money) continue;
            if(dp[next.pos][cost + next.cost] <= dtime + next.time) continue;
            
            q.push((node){next.pos, cost + next.cost, dtime + next.time});
            dp[next.pos][cost + next.cost] = dtime + next.time;
        }
    }
    
    int ret = INF;
    for(int i=0; i<=money; ++i)
        ret = min(ret, dp[nodes-1][i]);
    return ret;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);
        
        for(int i=0; i<n; ++i) adj[i].clear();
        
        while(k--){
            int u, v, x, d;
            scanf("%d %d %d %d", &u, &v, &x, &d);
            adj[u-1].push_back({v-1, x, d});
        }
    
        int r = dijkstra(n, m);
        if(r < INF) printf("%d\n", r);
        else puts("Poor KCM");
    }
    
    return 0;
}