这一题用到了状态压缩。然后接下来可以用 dp 或 dfs。

一开始我用的是 dp，不会，然后看题解，dp 写完感觉脑子糊糊的，于是打算写写 dfs。

dfs 优化后还是 WA 了一个点，然后又跑去看大佬的题解，发现了一个很玄学的优化方法，于是写在这边记录一下。

先看题：洛谷 P1433 吃奶酪

P1433 吃奶酪

题目描述

房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。

输入格式

第一行有一个整数，表示奶酪的数量 n。

第 2 到第 (n + 1) 行，每行两个实数，第 (i + 1) 行的实数分别表示第 i 块奶酪的横纵坐标 xi​,yi​。

输出格式

输出一行一个实数，表示要跑的最少距离，保留 22 位小数。

输入输出样例

输入 #1

4
1 1
1 -1
-1 1
-1 -1

输出 #1

7.41

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤n≤15，∣xi​∣,∣yi​∣≤200，小数点后最多有 3 位数字。

提示

对于两个点 (x1​,y1​)，(x2​,y2​)，两点之间的距离公式为

 这个优化方法就是卡时。

通过记录 dfs 深搜的次数，来判断程序运行的时间，当快要到达时间限制的时候就停止搜索。

那么保证答案正确的正确性会有些玄学，这里应该可以说经过较长时间的深搜，通过贪心保证目前获得的答案是之前搜索过的答案中最小的，那么它是正确答案的可能性就比较大了。

贴代码和注释。

/*
⣿⣆⠱⣝⡵⣝⢅⠙⣿⢕⢕⢕⢕⢝⣥⢒⠅⣿⣿⣿⡿⣳⣌⠪⡪⣡⢑
⣿⣿⣦⠹⣳⣳⣕⢅⠈⢗⢕⢕⢕⢕⢕⢈⢆⠟⠋⠉⠁⠉⠉⠁⠈⠼⢐
⢰⣶⣶⣦⣝⢝⢕⢕⠅⡆⢕⢕⢕⢕⢕⣴⠏⣠⡶⠛⡉⡉⡛⢶⣦⡀⠐
⡄⢻⢟⣿⣿⣷⣕⣕⣅⣿⣔⣕⣵⣵⣿⣿⢠⣿⢠⣮⡈⣌⠨⠅⠹⣷⡀
⡵⠟⠈⢀⣀⣀⡀⠉⢿⣿⣿⣿⣿⣿⣿⣿⣼⣿⢈⡋⠴⢿⡟⣡⡇⣿⡇
⠁⣠⣾⠟⡉⡉⡉⠻⣦⣻⣿⣿⣿⣿⣿⣿⣿⣿⣧⠸⣿⣦⣥⣿⡇⡿⣰
⢰⣿⡏⣴⣌⠈⣌⠡⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣬⣉⣉⣁⣄⢖⢕
⢻⣿⡇⢙⠁⠴⢿⡟⣡⡆⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣵
⣄⣻⣿⣌⠘⢿⣷⣥⣿⠇⣿⣿⣿⣿⣿⣿⠛⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿
⢄⠻⣿⣟⠿⠦⠍⠉⣡⣾⣿⣿⣿⣿⣿⣿⢸⣿⣦⠙⣿⣿⣿⣿⣿⣿⣿
⡑⣑⣈⣻⢗⢟⢞⢝⣻⣿⣿⣿⣿⣿⣿⣿⠸⣿⠿⠃⣿⣿⣿⣿⣿⣿⡿
⡵⡈⢟⢕⢕⢕⢕⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣿⣿⣿⣿⣿⠿⠋⣀
⣿⣿⣿⢻⣿⣿⣿⣿⠻⣿⣿⡿⠿⠿⠿⣿⠻⡿⠻⠿⣿⡟⠛⠛⢛⣿⣿
⣿⠏⣼⢸⡄⢿⢋⢸⣷⣇⢻⣿⣿⣿⣿⣿⡗⣥⠂⢦⣿⣭⢩⡍⣭⣽⣿
⣿⣾⣛⣸⣿⣾⣾⣈⣛⣠⣿⣤⣤⣤⣤⣼⣴⣫⣶⣌⣻⣋⣼⣇⣋⣼⣿
*/
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pr pair<int, int>
#define MOD 0x7fffffff
#define INF 0x7fffffff
#define N 1000005

inline int read() 
{
    int x = 0, neg = 1; char op = getchar();
    while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar();}
    while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar();}
    return neg * x;
}

double dis[20][20];

int n;

struct node
{
    double x, y;
} e[20];

struct snode
{
    int u; // 出发点
    double dist; // 路径长
    int step; // 路径压缩
};

double res = 1e30;

int l = 0;

void dfs(snode t)
{
    l++;  // 计算深搜次数
    if (t.step == (1 << n) - 1)
    {
        res = min(res, t.dist);
        return ;
    }
    if (t.dist >= res) return ; // 优化，只用这个会 WA 一个点 qwq    
    if (l > 30000000) return ; // 快达到时间限制时
    for (int i = 1; i <= n; i++)
    {
        if (t.step & (1 << (i - 1))) continue;
        snode now{i, t.dist + dis[t.u][i], t.step + (1 << (i - 1))};
        dfs(now);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> e[i].x >> e[i].y;
    }
    e[0].x = e[0].y = 0;
    for (int i = 0; i <= n; i++) // 初始化
    {
        for (int j = 0; j <= n; j++)
        {
            dis[i][j] = sqrt((e[i].x - e[j].x) * (e[i].x - e[j].x) + (e[i].y - e[j].y) * (e[i].y - e[j].y));
        }
    }
    dfs(snode{0, 0, 0});
    printf("%.2lf\n", res);
    return 0;
}