도로 포장

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

꽤 오래 생각하다가 답을 봤는데, 한 줄 읽고 뭔지 알겠는...그런 아쉬운 문제였다.

이 문제를 푸는 핵심은 다익스트라를 돌리되 DIST를 아래와 같이 2차원 배열로 관리해주는 것이다.

• DIST[k][n]: k개의 도로를 지워서 n번 정점에 도착할 때의 최소거리

이후에 priority queue를 사용해서 구현할 때 도로를 지울 때, 안 지울 때 두 가지 경우를 고려해서 넣어주면 된다.

이 때, 물론 pq에는 현재까지 몇 개의 도로를 지웠는지를 함께 유지해준다.

굳이 formal하게 증명을 해보자면 아래와 같이 생각해보는 것은 어떨까?

• 모든 정점에 대해서 0개 지우고 왔을 때, 1개 지우고 왔을 때, ... 와 같이 몇개를 지웠는지에 따라 정점을 복사하자
• n개 지우고 x에 왔을 때 -> n개 지우고 y에 왔을 때 간선의 비용은 주어진 비용이 될 것이다.
• n개 지우고 x에 왔을 때 -> n+1개 지우고 y에 왔을 때 간선의 비용은 0이 될 것이다.

#include <iostream>
#include <cstdint>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

const size_t kMaxN = 10000;
const size_t kMaxM = 50000;
const size_t kMaxK = 20;
const size_t kMaxW = 1000000;

size_t N, M, K;
vector<pair<size_t, size_t> > AL[kMaxN];

bool VISIT[kMaxN];
int64_t DIST[kMaxK + 1][kMaxN];

void Dijkstra(const size_t src)
{
  priority_queue<tuple<int64_t, size_t, size_t> > pq;

  DIST[0][src] = 0;
  pq.emplace(-DIST[0][src], src, 0);

  while (!pq.empty())
  {
    int64_t dist = -get<0>(pq.top());
    size_t here = get<1>(pq.top());
    size_t pave = get<2>(pq.top());
    pq.pop();

    if (DIST[pave][here] < dist)
    {
      continue;
    }

    for (const auto& neighbor : AL[here])
    {
      size_t there = neighbor.second;
      int64_t weight = static_cast<int64_t>(neighbor.first);

      // not pave
      if (dist + weight < DIST[pave][there])
      {
        DIST[pave][there] = dist + weight;
        pq.emplace(-DIST[pave][there], there, pave);
      }

      // pave
      if (pave < K && dist < DIST[pave + 1][there])
      {
        DIST[pave + 1][there] = dist;
        pq.emplace(-DIST[pave + 1][there], there, pave + 1);
      }
    }
  }
}

int main(void)
{
  // Initialize
  for (size_t i = 0; i < kMaxN; ++i)
  {
    VISIT[i] = false;
  }

  for (size_t i = 0; i < kMaxK + 1; ++i)
  {
    for (size_t j = 0; j < kMaxN; ++j)
    {
      DIST[i][j] = static_cast<int64_t>(kMaxW * kMaxN * 100);
    }
  }

  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  cin >> N >> M >> K;
  for (size_t it = 0; it < M; ++it)
  {
    size_t src, dst, weight;
    cin >> src >> dst >> weight;

    AL[src - 1].emplace_back(weight, dst - 1);
    AL[dst - 1].emplace_back(weight, src - 1);
  }

  // Solve
  Dijkstra(0);

  // Print answer
  int64_t ans = kMaxW * kMaxN * 100;
  for (size_t it = 0; it < kMaxK + 1; ++it)
  {
    ans = min(ans, DIST[it][N - 1]);
  }

  cout << ans << '\n';

  return 0;
}