10217번

10217번 - KCM Travel

이 문제도 이전 문제와 마찬가지로 다익스트라를 기반으로 한차원 늘려서 문제를 풀었다.

시간제한이 10초이기 때문에 시간도 넉넉했다.

dist[n][k] 라는 이차원 배열이 n노드까지 k원일때 최단거리라고 만들어서 문제를 풀 수 있었다.

그렇게 해서 다음 정점 노드의 시간값이 최소시간이고, 가격이 m원 이하일 때만 큐에 넣어서 다익스트라로 풀었다.

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef struct
{
    int to;
    int price;
    int time;
}E;
 
const int INF = 987654321;
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
    while (tc--)
    {
        int n, m, k;
        cin >> n >> m >> k;
 
        vector<vector<E>> v(n + 1);
 
        while (k--)
        {
            int from;
            E ed;
            cin >> from >> ed.to >> ed.price >> ed.time;
            v[from].push_back(ed);
        }
 
        vector<vector<int>> dist(n + 1,vector<int>(10001,INF));
 
        priority_queue<pair<pair<int,int>,int>> q;
        dist[1][0] = 0;
        q.push({ {0,1},0 });
 
        while (!q.empty())
        {
            int here = q.top().first.second;
            int cost_t = -q.top().first.first;
            int cost_p = q.top().second;
            q.pop();
 
            if (cost_t > dist[here][cost_p])
            {
                continue;
            }
 
            for (int i = 0; i < v[here].size(); i++)
            {
                int there = v[here][i].to;
                int c_cost_t = v[here][i].time;
                int c_cost_p = v[here][i].price;
 
                if (c_cost_p + cost_p <= m)
                {
                    if (dist[there][c_cost_p+cost_p] > c_cost_t + cost_t)
                    {
                        dist[there][c_cost_p + cost_p] = c_cost_t + cost_t;
                        q.push({ {-dist[there][c_cost_p + cost_p],there},c_cost_p + cost_p });
                    }
                }
            
            }
        }
        int minn = INF;
        for (int i = 0; i <= 10000; i++)
        {
            if (dist[n][i] < minn)
            {
                minn = dist[n][i];
            }
        }
 
        if (minn == INF)
        {
            cout << "Poor KCM\n";
        }
        else
        {
            cout << minn << "\n";
        }
    }
 
    return 0;
}