Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const double INF = 1e9 + 7; //бесконечность
- double x[20], y[20]; //координаты городов.
- //Заметим, что для N элементов существует 2^N возможных подмножеств (масок)
- //значением от 0 до 2^N - 1.
- //Можно просто возвести 2 в произвольную степень с помощью битового сдвига:
- //2^N = 1 << N
- double dp[1 << 20][20];
- //Расстояние между городами a и b
- double dst(int a, int b) {
- double dx = x[a] - x[b], dy = y[a] - y[b];
- return sqrt(dx * dx + dy * dy);
- }
- int main() {
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> x[i] >> y[i];
- }
- for (int mask = 0; mask < (1 << n); mask++) {
- for (int i = 0; i < n; i++) {
- dp[mask][i] = INF;
- }
- }
- dp[1][0] = 0; //Маска 1 содержит только нулевой элемент.
- vector<int> pr (n + 1, -1); // массив предков
- for (int mask = 2; mask < (1 << n); mask++) {
- for (int i = 0; i < n; i++) {
- if ((mask >> i) & 1) { //Если mask содержит i
- int mask_without_i = mask ^ (1 << i);
- for (int j = 0; j < n; j++) {
- if (j != i && ((mask >> j) & 1)) { //Если j != i и mask содержит j
- if (dp[mask][i] > dp[mask_without_i][j] + dst(j, i)) {
- // запоминаем
- dp[mask][i] = dp[mask_without_i][j] + dst(j, i);
- pr[i] = j;
- }
- }
- }
- }
- }
- }
- double ans = INF;
- int last_index = -1;
- int mask_all = (1 << n) - 1; //маска, содержащая все элементы
- for (int i = 0; i < n; i++) {
- if (ans > dp[mask_all][i] + dst(i, 0)) {
- ans = dp[mask_all][i] + dst(i, 0);
- last_index = i;
- }
- }
- cout << ans << endl;
- if (last_index != -1) {
- // восстанавливаем путь
- // путь выведется в обратном порядке, но нам это не важно, так как
- // всё равно начинаем и заканчиваем и начинаем в одной и той же вершине (делаем круг)
- int ind = last_index;
- while (ind != -1) {
- cout << ind << " ";
- ind = pr[ind];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement