텔레포트

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

마치 입력이 그리드인 것 처럼 주어져서 조금 혼란스러웠으나, 고려할 가치가 있는 정점이 어디인가에 집중하면 쉽게 풀어줄 수 있다.

아래와 같은 노테이션을 활용하도록하자.

• (Xs, Ys): 시작점
• (Xe, Ye): 도착점
• (X11, Y11): 1번 텔레포트 중 한 쪽 입구
• (X12, Y12): 1번 텔레포트 중 다른 한 쪽 입구
• (X21, Y21): 2번 텔레포트 중 한 쪽 입구
• (X22, Y22): 2번 텔레포트 중 다른 한 쪽 입구
• (X31, Y31): 3번 텔레포트 중 한 쪽 입구
• (X32, Y32): 3번 텔레포트 중 다른 한 쪽 입구

위에 언급한 총 8개의 정점 중 서로 다른 2개의 정점을 뽑는다고 해보자.

이때, 우리는 서로 다른 두 정점의 거리를 항상 확실하게 알 수 있다.

• 같은 텔레포트의 서로 다른 두 정점이 골라진 경우 비용은 10일 것이고,
• 아닌 경우, 두 정점 사이의 맨하탄 디스턴스가 곧 비용이 될 것이다.

위와 같이 입력을 8개 정점의 그래프로 표현하고 최단 거리 알고리즘을 수행하면 된다.

입력이 작아서 플로이드가 더 좋은 선택이 될 것 같지만, 기억도 살릴 겸 다익스트라를 써보았다.

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

const int kS = 0;
const int kE = 1;
const int kT11 = 2;
const int kT12 = 3;
const int kT21 = 4;
const int kT22 = 5;
const int kT31 = 6;
const int kT32 = 7;
const int kN = 8;

int64_t Dijkstra(const vector<vector<pair<int, int>>>& adj, const int src, const int dst)
{
  vector<int64_t> min_dist(adj.size(), numeric_limits<int64_t>::max());
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;

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

  while (!pq.empty())
  {
    int here = pq.top().second;
    int64_t dist = pq.top().first;
    pq.pop();

    if (dist > min_dist[here])
    {
      continue;
    }

    for (const auto& neighbor : adj[here])
    {
      int there = neighbor.first;
      int cost = neighbor.second;

      if (dist + cost < min_dist[there])
      {
        min_dist[there] = dist + cost;
        pq.emplace(min_dist[there], there);
      }
    }
  }

  return min_dist[dst];
}

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

  // Read input
  vector<pair<int, int>> vertices(kN);
  for (int i = 0; i < kN; ++i)
  {
    cin >> vertices[i].first;
    cin >> vertices[i].second;
  }

  // Build adjacency list
  vector<vector<pair<int, int>>> adj(kN, vector<pair<int, int>>());
  for (int src = 0; src < kN; ++src)
  {
    for (int dst = src + 1; dst < kN; ++dst)
    {
      int man_dist = abs(vertices[src].first - vertices[dst].first) + abs(vertices[src].second - vertices[dst].second);
      adj[src].emplace_back(dst, man_dist);
      adj[dst].emplace_back(src, man_dist);

      if ((src == kT11 && dst == kT12) || (src == kT12 && dst == kT11))
      {
        adj[src].emplace_back(dst, 10);
        adj[dst].emplace_back(src, 10);
      }

      if ((src == kT21 && dst == kT22) || (src == kT22 && dst == kT21))
      {
        adj[src].emplace_back(dst, 10);
        adj[dst].emplace_back(src, 10);
      }

      if ((src == kT31 && dst == kT32) || (src == kT32 && dst == kT31))
      {
        adj[src].emplace_back(dst, 10);
        adj[dst].emplace_back(src, 10);
      }
    }
  }

  // Solve
  cout << Dijkstra(adj, kS, kE) << '\n';

  return 0;
}