原题链接
这题我是用了个玄学的(dfs)剪枝跑过，如果要看正解状压(DP)，可以移步机房大佬的博客（传送门）
关于剪枝，具体的直接在代码里说吧。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20;
int ne[N][N], dis[N][N], chu[N], de[N], q[N], lev[N], l, o, rem, mi = 1e9, n;
//邻接矩阵存图，ne表示该点所指向的点，chu是该点的出度，dis是该点与下一个点之间的距离
//q是dfs搜索的队列，即已经拓展的点，l是队列q的长度，lev是点的深度，即题面中的K，rem用于关键剪枝
//mi储存最优解，o为sort的compare函数里所用
inline int re()//快读
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
bool comp(int x, int y)//sort的compare函数，根据两点间距离进行排序
{
return dis[o][x] < dis[o][y];
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
void dfs(int fir, int nxt, int s, int po)
{
if (!(po ^ n))//如果n个点都被拓展了，就更新答案
{
mi = minn(mi, s);
return;
}
if (s >= mi)//最优解剪枝
return;
int i, j, x, y;
for (i = fir; i <= l; i++)//从队列的第fir个点开始尝试
{
if (s + rem * lev[x = q[i]] >= mi)//若当前解加上理论最优解依然不能更新答案，那么舍去
continue;
for (j = nxt; j <= chu[x]; j++)//从这个点能到达的点中的第nxt个点开始尝试拓展
if (!lev[y = ne[x][j]])//如果没有被拓展
{
lev[y] = lev[x] + 1;//将该点拓展
q[++l] = y;
rem -= dis[y][ne[y][1]];//更新理论最优解
dfs(i, j + 1, s + dis[x][y] * lev[x], po + 1);
l--;//回溯
lev[y] = 0;
rem += dis[y][ne[y][1]];
}
nxt = 1;//注意要搜下一个点的时候需重新从第1个点开始尝试
}
}
int main()
{
int i, m, x, y, z;
n = re();
m = re();
memset(dis, 60, sizeof(dis));
for (i = 1; i <= m; i++)
{
x = re();
y = re();
z = re();
if (dis[x][y] > 1e9)
{
ne[x][++chu[x]] = y;
ne[y][++chu[y]] = x;
}
dis[x][y] = dis[y][x] = minn(dis[x][y], z);
}
for (o = 1; o <= n; o++)
{
sort(ne[o] + 1, ne[o] + chu[o] + 1, comp);//根据距离对点o所能到达的点进行排序
rem += dis[o][ne[o][1]];//将每个点到其它点的最近距离累加起来，就是取n条边的理论最优解
}
for (i = 1; i <= n; i++)
{
q[1] = i;//将第i个点作为出发点，加入队列
rem -= dis[i][ne[i][1]];//要减去该点到其它点的最近距离，剩下的才是对于未拓展点的理论最优解，即假设剩下每个点到其它点的最近距离都是连在该点上
l = lev[i] = 1;//初始化队列长和深度
dfs(1, 1, 0, 1);
lev[i] = 0;//回溯
rem += dis[i][ne[i][1]];
}
printf("%d", mi);
return 0;
}