[BOJ] 1162번: 도로포장

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

벽 부수기 문제와 비슷하다. 주어만 바뀐 느낌이고 트리 구조(?)에서 그래프로 바뀐 것 뿐이다.

도로를 포장하거나 안 하거나 두 가지 경우가 있으므로 그 두 가지 경우를 모두 확인해주면 된다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

struct Edg {
    int idx, cnt;
    long long dst;
    Edg(int idx, long long dst) : idx(idx), dst(dst) {}
    Edg(int idx, long long dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {}
    bool operator<(const Edg& a) const { return a.dst < dst; }
};

const int MN = 10000 + 1;

int N, M, K;
vector<Edg> v[MN];
long long dist[MN][21];

int main()
{
    memset(dist, 0x3f, sizeof dist);
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 0, f, t, w; i < M; ++i) {
        scanf("%d %d %d", &f, &t, &w);
        v[f].push_back({ t, w });
        v[t].push_back({ f, w });
    }

    dist[1][0] = 0;
    priority_queue<Edg> pq;
    pq.push({1, 0, 0});

    while (!pq.empty()) {
        auto now = pq.top();
        pq.pop();

        for (auto& nxt : v[now.idx]) {
            if (dist[nxt.idx][now.cnt] > nxt.dst + now.dst) {
                dist[nxt.idx][now.cnt] = nxt.dst + now.dst;
                pq.push({ nxt.idx, dist[nxt.idx][now.cnt], now.cnt });
            }
            if (now.cnt + 1 <= K && dist[nxt.idx][now.cnt + 1] > now.dst) {
                dist[nxt.idx][now.cnt + 1] = now.dst;
                pq.push({ nxt.idx, now.dst, now.cnt + 1});
            }
        }
    }

    long long ret = 1e15;
    for (int i = 0; i <= K; ++i) {
        ret = min(ret, dist[N][i]);
    }
    printf("%lld\n", ret);
    return 0;
}