题目链接：https://acm.uestc.edu.cn/problem/oyhuan-you-shi-jie/description

题目大意：求遍历所有点的最短距离

分析：

这道题很明显是状态压缩dp。

首先把点抽象化成一个顶点，点之间的距离变成边的权值。

然后就是常规状态压缩的写法了。

用一个数S的二进制来记录是否访问过某个点，然后暴力枚举每个点的每条边。

若可以访问，就继续递归下去，否则就返回。

记忆化搜索降低复杂度。

代码：

#include <bits/stdc++.h>
using namespace std;
struct node
{
	long long x, y;
}nodes[17];
long long g[17][17];
long long n, s;
const long long INF = 100000000000000ll;
long long dp[1 << 17][17];
long long solve(long long S, long long v)
{
	if (dp[S][v] >= 0)
	{
		return dp[S][v];
	}
	if (S == (1ll << n)-1)
	{
		return dp[S][v] = 0;
	}
	long long res = INF;
	for (int i = 0; i < n; ++i)
	{
		if (!(S >> i & 1))
		{
			res = min(res, solve(S | 1ll << i, i) + g[v][i]);
		}
	}
	return dp[S][v] = res;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	fill(g[0],g[0]+17*17,INF);
	cin >> n >> s;
	for (long long i = 0; i < n; ++i)
	{
		cin >> nodes[i].x >> nodes[i].y;
	}
	for (long long i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			g[i][j] = abs(nodes[i].x - nodes[j].x) + abs(nodes[i].y - nodes[j].y);
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << solve(0,s-1);
	//system("pause");
	return 0;
}