problem
有$n$个点,$m$条无向边，选择一个点开始开辟道路。开辟一条长度为$L$的链接$u，v$的道路会花费$L \times K$，K表示从选择的最初点到$u$所经过的点的数量。
solution
因为n比较小，所以可以状态压缩。第$i$位为1表示当前已经开辟了第$i$个点。枚举一个最初的状态，然后每次枚举下一个开辟的边得到下一个状态，转移即可。
转移的过程中要维护出每个状态到初始点的距离。
code
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1 << 13;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int dis[110][110];
int n,m,f[N],a[N][14],vis[N];
queue<int>q;
int solve(int x) {
memset(f,0x3f,sizeof(f));
memset(a,0x3f,sizeof(a));
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;++i) {
if(x >> (i - 1) & 1) {
a[x][i] = 1;break;
}
}
f[x] = 0;
vis[x] = 1;
q.push(x);
while(!q.empty()) {
int u = q.front();q.pop();
for(int i = 1;i <= n;++i) {
if(u >> (i - 1) & 1) {
for(int j = 1;j <= n;++j) {
if(u >> (j - 1) & 1) continue;
int v = u | (1 << (j - 1));
if(dis[i][j] != 0x3f3f3f3f && f[v] > f[u] + a[u][i] * dis[i][j]) {
f[v] = f[u] + a[u][i] * dis[i][j];
for(int k = 1;k <= n;++k) a[v][k] = a[u][k];
a[v][j] = a[u][i] + 1;
if(!vis[v]) q.push(v),vis[v] = 1;
}
}
}
}
}
return f[(1 << n) - 1];
}
int main() {
n = read(),m = read();
memset(dis,0x3f,sizeof(dis));
for(int i = 1;i <= m;++i) {
int u = read(),v = read(),w = read();
dis[v][u] = dis[u][v] = min(dis[u][v],w);
}
int ans = 1e9;
for(int i = 0;i < n;++i) ans = min(ans,solve(1 << i));
cout<<ans;
return 0;
}