[백준 10217번] KCM Travel

문제 링크: https://www.acmicpc.net/problem/10217

10217번: KCM Travel

<문제 풀이> 다익스트라, DP 알고리즘

 

j의 비용을 사용해서 i번 정점까지의 최단 거리를 저장할 2차원 DP[i][j] 배열을 만들고 다익스트라 알고리즘을 사용하면 됩니다.

 

최단 거리를 구할 때 2가지 최적화 방법을 적용할 수 있습니다.

 

1.

정점 u를 비용 c로 방문하여 최단 거리를 갱신할 때, 비용 c보다 큰 비용으로 정점 u를 방문하는 경우는 고려하지 않아도 됩니다. 그 이유는 정점 u에 비용 c로 도달한 상황에서 이미 최단 거리를 갱신했다면, c보다 큰 비용으로 해당 정점을 방문하는 것은 최적의 경로가 될 수 없기 때문입니다. 이를 통해 우선순위큐에 불필요한 삽입을 줄일 수 있습니다.

 

2. 

각 정점에 연결된 간선들을 비용 기준으로 오름차순 정렬합니다. 다익스트라 알고리즘을 사용하여 다음 정점을 탐색할 때, 해당 정점까지의 비용 cost가 최대 지원 비용 M을 초과하는 경우, 그 이후의 간선들은 검사할 필요가 없습니다.

 

 

  

 

<C++소스코드>

#include<iostream>
#include<vector>
#include<tuple>
#include<queue>
#include<functional>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAX_N = 100;
const int MAX_M = 10000;
const int INF = 0x3f3f3f3f;
int N, M, K;
int dist[MAX_N + 1][MAX_M + 1];
vector<tuple<int, int, int> > adj[MAX_N + 1];

bool CmpCost(tuple<int, int, int>& a, tuple<int, int, int>& b) {
    return get<1>(a) < get<1>(b);
}

void init() {
    for (int i = 0; i <= N; i++) {
        adj[i] = {};
    }
    memset(dist, 0x3f, sizeof(dist));
}

int dijkstra(int st) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > pq;
    dist[st][0] = 0;
    pq.push({ dist[st][0], 0, st });
    while (!pq.empty()) {
        int cur_dist, cur_cost, cur_idx;
        tie(cur_dist, cur_cost, cur_idx) = pq.top(); pq.pop();

        if (dist[cur_idx][cur_cost] != cur_dist) continue;

        for (auto& nxt : adj[cur_idx]) {
            int d, c, v; tie(d, c, v) = nxt;
            int nxt_dist = cur_dist + d;
            int nxt_cost = cur_cost + c;
            int nxt_idx = v;

            if (nxt_cost > M) break;

            if (nxt_dist < dist[nxt_idx][nxt_cost]) {
                for (int i = nxt_cost; i <= M; i++) {
                    if (dist[nxt_idx][i] <= nxt_dist) break;
                    dist[nxt_idx][i] = nxt_dist;
                }
                pq.push({ dist[nxt_idx][nxt_cost], nxt_cost, nxt_idx });
            }
        }
    }
    int ret = INF;
    for (int i = 0; i <= M; i++) {
        ret = min(ret, dist[N][i]);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int test_case; cin >> test_case;
    while (test_case--) {
        init();
        cin >> N >> M >> K;
        for (int i = 0; i < K; i++) {
            int u, v, c, d; cin >> u >> v >> c >> d;
            adj[u].push_back({ d, c, v });
        }
        for (int i = 1; i <= N; i++) {
            sort(adj[i].begin(), adj[i].end(), CmpCost);
        }
        int ans = dijkstra(1);
        if (ans >= INF) cout << "Poor KCM\n";
        else cout << ans << '\n';
    }

    return 0;
}