문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 최단 경로를 구하는데 중간에 cost라는 옵션이 하나 추가된다.
  • 때문에 단순히 다익스트라를 한번 진행하면서 풀기는 쉽지 않다.
  • 이 문제는 우선순위 큐를 이용해서 공항, 비용, 거리 정보를 모두 보내주면서 최종 지점인 n에 도착했을 때 계속해서 최솟값을 찾아준다.

유의점 및 힌트

  • 근데 BFS 이용할 때 문제는 중복되는 값이 계속해서 들어온다는 것이다.
  • 같은 거리의 다른 비용이 드는 정보들이 마구마구 큐에 들어온다.
  • 결국 메모리 초과를 발생시킨다!
  • 그래서 찾아보던 중 DP를 이용하는 방법이 있었다.

여기서 DP를(?)

  • 한 공항까지의 거리에 대한 비용을 저장한다면 비용이 작게 들어올 때만 큐에 넣어줌으로써 중복을 예방할 수 있다.
  • 이게 가능한 이유는 최대거리는 10000이라고 되어있기 때문이다!

코드

#include <cstdio>
#include <vector>
#include <queue>
#define pii pair<int, int>
#define pip pair<int, pii>
#define X first
#define Y second
#define D Y.X
#define C Y.Y
#define INF 10000000
using namespace std;


char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

int t, n, m, k, u, v, d, c, ans;

int main(){
    t = readInt();
    while(t--){
        ans = INF;
        n = readInt(), m = readInt(), k = readInt();
        vector<vector<pip> >adj(n + 1);
        vector<vector<int> > dist(101, vector<int>(10001, INF));
        while(k--){
            u =readInt(), v = readInt(), c = readInt(), d = readInt();
            adj[u].push_back(pip(v, pii(d, c)));
        }
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        dist[1][0] = 0;
        pq.push(pii(0, 1));
        while(!pq.empty()){
            pii top = pq.top(); pq.pop();
            int ti = top.Y, tc = top.X;
            int td = dist[ti][tc];
            if(ti == n){
                ans = min(td, ans);
                continue;
            }
            for(int i = 0; i < adj[ti].size(); i++){
                int ni = adj[ti][i].X, nc = tc + adj[ti][i].C, nd = adj[ti][i].D + td;
                if(nc > m || nd >= ans) continue;
                if(dist[ni][nc] > nd){
                    dist[ni][nc] = nd;
                    pq.push(pii(nc, ni));
                }
            }
        }
        if(ans == INF) printf("Poor KCM\n");
        else printf("%d\n", ans);     
    }
}

느낀점

  • DP를 떠올려서 이런 문제를 해결한다는 것… 경의롭다..
  • 오늘도 한대 맞고 갑니다..ㅎㅎ 나도 떠올릴 수 있는 날이 올까 ㅋㅋ