题面
n <= 50000，m <= 200000，k <= 12
题解
可以从K条边的两端和1结点出发各进行一次O(nlogn)的Dijk，然后就浓缩成了一个最多只有25个点的小完全图，然后就像旅行商问题一样，用状态压缩DP做。
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#define LL long long
using namespace std;
int read() {
int f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}
while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}
return x * f;
}
struct it{
int v;
LL w;
it(){}
it(int V,LL W){v = V;w = W;}
};
bool operator < (it a,it b) {
return a.w < b.w;
}
vector<it> g[50005];
vector<it> g2[50];
int n,m,i,j,s,o,k,K,e;
LL dp[30][50005],ans;
LL dp2[1<<14][30];
LL ed[30][30];
int u[17],v[17];
LL wi[17];
bool f[50005];
LL tre[200005];
LL min(LL a,LL b) {
return a < b ? a : b;
}
void maketree(int n) {
m = 1;
while(m < n + 2) m <<= 1;
for(int i = m + n + 3;i > 0;i --) {
tre[i] = 1e18;
}
}
void addtree(int x,LL y) {
int s = x + m;
tre[s] = y;
s /= 2;
while(s) {
tre[s] = min(tre[s * 2],tre[s * 2 + 1]);
s /= 2;
}
return ;
}
int searchtree(int s) {
if(s >= m) return s - m;
if(tre[s * 2] < tre[s * 2 + 1]) return searchtree(s * 2);
return searchtree(s * 2 + 1);
}
LL findtree(int l,int r) {
int s = m + l - 1;
int t = m + r + 1;
LL ans = 1e18;
while(s || t) {
if(s / 2 != t / 2) {
if(s % 2 == 0) {
ans = min(ans,tre[s + 1]);
}
if(t % 2) {
ans = min(ans,tre[t - 1]);
}
}
else break;
s >>= 1;
t >>= 1;
}
return ans;
}
void dfs(int x,int ad,LL as) {
// printf("->%d %lld\n",x % 2 ? v[x/2]:u[x/2],as);
if(as >= ans) return ;
if(ad > K * 2) {
for(int i = 0;i < g2[x].size();i ++) {
if(g2[x][i].v == 1) {
as += g2[x][i].w;
break;
}
}
ans = min(ans,as);
return ;
}
f[x] = 1;
bool flag = 0;
if(x % 2) {
if(!f[x - 1]) dfs(x - 1,ad + 1,as + wi[x / 2]);
else flag = 1;
}
else {
if(!f[x + 1]) dfs(x + 1,ad + 1,as + wi[x / 2]);
else flag = 1;
}
if(flag) {
for(int i = 0;i < g2[x].size();i ++) {
if(!f[g2[x][i].v]) {
dfs(g2[x][i].v,ad + 1,as + g2[x][i].w);
}
}
}
f[x] = 0;
return ;
}
int main() {
n = read();e = read();K = read();
v[0] = 1;
for(int i = 1;i <= e;i ++) {
s = read();o = read();k = read();
g[s].push_back(it(o,k));
g[o].push_back(it(s,k));
if(i <= K) u[i] = s,v[i] = o,wi[i] = k;
}
for(int k = 1;k <= K * 2 + 1;k ++) {
for(int i = 1;i <= n;i ++) dp[k][i] = 1e18;
int ad = (k % 2 ? v[k / 2] : u[k / 2]);
maketree(n);
memset(f,0,sizeof(f));
dp[k][ad] = 0;
addtree(ad,0);
for(int i = 1;i < n;i ++) {
int t = searchtree(1);
f[t] = 1;
addtree(t,1e18);
for(int j = 0;j < g[t].size();j ++) {
if(!f[g[t][j].v]) {
dp[k][g[t][j].v] = min(dp[k][g[t][j].v],dp[k][t] + g[t][j].w);
addtree(g[t][j].v,dp[k][g[t][j].v]);
}
}
}
}
for(int i = 1;i < K * 2 + 1;i ++) {
for(int j = i + 1;j <= K * 2 + 1;j ++) {
int a = (i % 2 ? v[i / 2] : u[i / 2]);
int b = (j % 2 ? v[j / 2] : u[j / 2]);
g2[i].push_back(it(j,dp[i][b]));
g2[j].push_back(it(i,dp[i][b]));
ed[i][j] = dp[i][b];
ed[j][i] = dp[j][a];
// printf("%d %d -- %lld(%lld)\n",a,b,dp[i][b],dp[j][a]);
}
sort(g2[i].begin(),g2[i].end());
}
ans = 1e18;
memset(f,0,sizeof(f));f[0] = 1;
for(int i = 2;i <= 1<<(K + 1);i ++)
for(int j = 1;j <= K * 2 + 1;j ++) dp2[i][j] = 1e18;
for(int j = 2;j <= K * 2 + 1;j ++) dp2[1][j] = 1e18;
// printf("%lld\n",dp2[1][1]);
for(int k = 1;k < 1<<(K + 1);k += 2) {
for(int i = k == 1 ? 1 : 2;i <= K * 2 + 1;i ++) {
if(k & (1<<(i / 2))) {
// printf("(%d,%d):%lld\n",k,a,dp2[k][a]);
for(int j = 2;j <= K * 2 + 1;j ++) {
if(int(j/2) != int(i/2) && (k & (1<<(j / 2))) == 0) {
dp2[k | (1<<(j/2))][j] = min(dp2[k | (1<<(j/2))][j],dp2[k][i] + ed[i][j + 1 - (j % 2 ? 2:0)] + wi[(j/2)]);
}
}
}
}
}
for(int i = 2;i <= K * 2 + 1;i ++) {
ans = min(ans,dp2[(1<<(K + 1)) - 1][i] + dp[i][1]);
// cout<<"*"<<((1<<(K + 1)) - 1)<<endl;
}
printf("%lld\n",ans);
return 0;
}
