test/aoj/DPL_2_C/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_C
• Link: View error logs on GitHub Actions

Depends on

• Bitonic tour (Mylib/DynamicProgramming/bitonic_tour.cpp)
• Input tuple vector (Mylib/IO/input_tuple_vector.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_C"
#define ERROR 0.0001

#include <iomanip>
#include <iostream>
#include <vector>
#include "Mylib/DynamicProgramming/bitonic_tour.cpp"
#include "Mylib/IO/input_tuple_vector.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n;
  std::cin >> n;

  auto [x, y] = hl::input_tuple_vector<int, int>(n);

  std::cout << std::fixed << std::setprecision(12) << hl::bitonic_tour(n, x, y) << std::endl;

  return 0;
}

#line 1 "test/aoj/DPL_2_C/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_C"
#define ERROR 0.0001

#include <iomanip>
#include <iostream>
#include <vector>
#line 2 "Mylib/DynamicProgramming/bitonic_tour.cpp"
#include <algorithm>
#include <cmath>
#include <limits>
#line 6 "Mylib/DynamicProgramming/bitonic_tour.cpp"

namespace haar_lib {
  template <typename T>
  double bitonic_tour(int n, const std::vector<T> &x, const std::vector<T> &y) {
    std::vector<std::vector<double>> dist(n, std::vector<double>(n));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        double dx  = x[i] - x[j];
        double dy  = y[i] - y[j];
        dist[i][j] = std::sqrt(dx * dx + dy * dy);
      }
    }

    std::vector<std::vector<double>> dp(n, std::vector<double>(n, std::numeric_limits<double>::max()));

    dp[0][0] = 0;

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        dp[i][i] = std::min(dp[i][i], dp[i][j] + dist[i][j]);
        if (i + 1 < n) {
          dp[i + 1][j] = std::min(dp[i + 1][j], dp[i][j] + dist[i][i + 1]);
          dp[i][i + 1] = std::min(dp[i][i + 1], dp[i][j] + dist[j][i + 1]);
        }
        if (j + 1 < n) {
          dp[i][j + 1] = std::min(dp[i][j + 1], dp[i][j] + dist[j][j + 1]);
          dp[j + 1][j] = std::min(dp[j + 1][j], dp[i][j] + dist[i][j + 1]);
        }
      }
    }

    return dp[n - 1][n - 1];
  }
}  // namespace haar_lib
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuple_vector.cpp"
#include <tuple>
#include <utility>
#line 7 "Mylib/IO/input_tuple_vector.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
  }

  template <typename T, size_t... I>
  void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
  }

  template <typename... Args>
  auto input_tuple_vector(int N) {
    std::tuple<std::vector<Args>...> ret;

    input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
    for (int i = 0; i < N; ++i) {
      input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
    }

    return ret;
  }
}  // namespace haar_lib
#line 9 "test/aoj/DPL_2_C/main.test.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n;
  std::cin >> n;

  auto [x, y] = hl::input_tuple_vector<int, int>(n);

  std::cout << std::fixed << std::setprecision(12) << hl::bitonic_tour(n, x, y) << std::endl;

  return 0;
}

Back to top page