01162번 도로포장

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

Keywords: Dijkstra Algorithm

USACO 답게 문제 퀄리티가 꽤 좋았어서, 부계로 문제 다시 풀기를 시작하면서 가장 먼저 기억이 났던 것 같다.

아마도 문제 퀄리티가 좋다고 기억하고 있는 이유는 (1)쉬우면서, (2)문제 description이 꽤나 흥미진진해서인 것 같다.

풀이방법은 Dijkstra algorithm을 사용하되, 아래와 같이 distance 배열을 관리해주는 것이다.

DIST[i][j] : i번 도시에 j개 도로를 포장하여 도달할 때의 최단시간

Dijkstra algoritm에서 이번에 고려하고 있는 도시를 here 인접한 도시들 중 하나를 there이라고 하자.

일반적인 Dijkstra algorithm과 동일하게 진행하되, here에서 there로 도로를 포장하며 이동하는 경우를 추가적으로 고려해주면 된다.

한편, 이 방법은 실질적으로는 N개 도시를 N * (K + 1)개 도시로 뻥튀기(?)시켜준 것으로 이해할 수 있다(굳이 아래와 같이 예를 들지 않아도, DIST 배열의 생김새를 보면 바로 알 수 있다).

e.g. 0개 포장 후 1번 도시, 1개 포장 후 1번 도시, …, K개 포장 후 1번 도시

나는 풀이에서 priority queue를 사용해서 Dijkstra algorithm을 구현하였으므로 복잡도는 \(\|E\|lg\|E\|\) 가 될 것인데, 위와 동일한 논리로 간선의 수는 M개에서 M * (K + 1)개가 된 것으로 볼 수 있다.

문제에 주어진 최대 M, K의 범위를 고려하면 제시한 알고리즘은 시간 내에 풀리리라.

아래는 솔루션이다.

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

// Inputs.
int N, M, K;
vector<vector<pair<int, int>>> ADJ;

// Solution.
vector<vector<int64_t>> DIST;

int64_t Solve(void) {
  // Initialize data structures.
  // DIST[i][j] = minimum distance to `i` using `j` paved roads.
  DIST.resize(N + 1, vector<int64_t>(K + 1, numeric_limits<int64_t>::max()));

  // Declare a min heap.
  using Element = pair<int64_t, pair<int, int>>;
  priority_queue<Element, vector<Element>, greater<Element>> pq;

  DIST[1][0] = 0;
  pq.emplace(DIST[1][0], make_pair(1, 0));
  while (!pq.empty()) {
    const auto dist = pq.top().first;
    const auto here = pq.top().second.first;
    const auto paved = pq.top().second.second;
    pq.pop();

    if (DIST[here][paved] < dist) {
      continue;
    } else {
      for (const auto& edge : ADJ[here]) {
        const auto& there = edge.first;
        const auto& weight = edge.second;
        // Consider not paving the road.
        if (dist + weight < DIST[there][paved]) {
          DIST[there][paved] = dist + weight;
          pq.emplace(DIST[there][paved], make_pair(there, paved));
        }
        // COnsider paving the road.
        if (paved < K && dist < DIST[there][paved + 1]) {
          DIST[there][paved + 1] = dist;
          pq.emplace(DIST[there][paved + 1], make_pair(there, paved + 1));
        }
      }
    }
  }

  int64_t answer = numeric_limits<int64_t>::max();
  for (int i = 0; i <= K; ++i) {
    answer = min(answer, DIST[N][i]);
  }

  return answer;
}

int main(void) {
  // For faster input.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  // Read inputs.
  cin >> N >> M >> K;
  ADJ.resize(N + 1);
  for (int i = 0; i < M; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    ADJ[u].emplace_back(v, w);
    ADJ[v].emplace_back(u, w);
  }

  // Print the answer.
  cout << Solve() << endl;

  return 0;
}