10217번 KCM Travel

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

나는 처음에 기존 money[Max]라는 배열을 통해

money 배열도 dist 배열(처음에는 1차원 배열)처럼 똑같이 다익스트라로 활용하였다.

그러나 계속 안 풀려서 결국 아이디어를 얻었다.

아이디어는 기존 다익스트라에서 한 차원 더 늘리는 것이었다.

dist[정점][현재 돈] = 거리

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 111
#define INF 987654321
 
typedef struct info
{
    int next, money, distance;
}info;
 
int n, m, k, dist[Max][10001];
vector<info> v[Max];
 
int dijstra(int start)
{
    for (int i = 0; i < Max; i++) {
        fill(dist[i], dist[i] + 10001, INF); // dist[i] + Max라고 했었다.
    }
 
    dist[start][0] = 0;
 
    priority_queue<pair<pair<int, int>, int > > pq;
    pq.push({ {0, start}, 0 });
 
    while (!pq.empty())
    {
        int here = pq.top().first.second;
        int distance = -pq.top().first.first;
        int cost = pq.top().second;
 
        pq.pop();
 
        if (dist[here][cost] < distance) continue;
 
        for (auto i : v[here]) {
            int next = i.next;
            int next_cost = i.money;
            int next_distance = i.distance;
 
            // 문제 조건
            if (cost + next_cost > m) continue;
 
            int sum = cost + next_cost;
 
            // dist[here][cost] 말고, distance라고 써도 된다.
            if (dist[next][sum] > dist[here][cost] + next_distance) {            
                dist[next][sum] = dist[here][cost] + next_distance;
                pq.push({ {-dist[next][sum], next}, sum });
            }
        }
    }
 
    int ret = -1;
 
    // m 이하까지 비용 사용 가능
    for (int i = 0; i <= m; i++) {
        if (dist[n][i] != INF) {
            ret = min(ret, dist[n][i]);
        }
    }
 
    return ret;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
 
    int T = 0;
    scanf("%d", &T);
 
    while (T--)
    {
        int u, vc, c, d;
 
        for (int i = 0; i < Max; i++) {
            v[i].clear();
        }
 
        scanf("%d %d %d", &n, &m, &k);
 
        for (int i = 0; i < k; i++) {
            scanf("%d %d %d %d", &u, &vc, &c, &d);
            v[u].push_back({ vc, c, d });
        }
 
        int g = dijstra(1);
 
        if (g == -1) printf("Poor KCM\n");
        else printf("%d\n", g);
    }
 
    return 0;
}