Bitonic tour
(Mylib/DynamicProgramming/bitonic_tour.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

Notes

Problems

References

Verified with

• test/aoj/DPL_2_C/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>

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/DynamicProgramming/bitonic_tour.cpp"
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>

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

Back to top page