搬迁Relocation

发表于 | 更新于 | 评论数：

最短路+状压dp

由于我们看到他的k很小（1<=k<=5）就想到了爆搜状压

我们肯定要知道k个城镇与每个点之间的距离，最短路就跑k遍；

枚举选的农场，开始状压；

至于状压：

1
2
3
4
5
6
f [当前状态为i (二进制中，1表示走过)]  [当前所在的城镇为j]
= f[i^(1<<(j-1))][p] + dis[p][j] (p为之前所在的城镇)

初始时：f[1<<(k-1)][k] = dis[k][s](s为选的农场，k为第一个经过的城镇)

最后枚举最后所在的城镇，加上他到选的农场的距离，取最小值；

具体见代码，大佬勿喷qwq。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,wz[6];
long long tot,head[10005],nx[100005],to[100005],w[100005];
long long dis[6][10005],vis[10005],f[2005][6];
void jia(long long aa,long long bb,long long cc)
{
	tot++;
	nx[tot]=head[aa];
	to[tot]=bb;
	w[tot]=cc;
	head[aa]=tot;
	return;
}
struct node
{
	long long id,val;
};
bool operator <(node aa,node bb)
{
	return aa.val>bb.val;
}
node bh(long long aa,long long bb)
{
	node tt;
	tt.id=aa;
	tt.val=bb;
	return tt;
}
void spfa(long long rt)//其实是dijkstra。。。
{
	priority_queue<node>q;
	q.push(bh(wz[rt],0));
	memset(vis,0,sizeof(vis));
	dis[rt][wz[rt]]=0;
	while(!q.empty())
	{
		node kk=q.top();
		q.pop();
		if(vis[kk.id]) continue;
		vis[kk.id]=1;
		for(long long i=head[kk.id];i;i=nx[i])
		{
			long long yy=to[i];
			if(dis[rt][yy]>dis[rt][kk.id]+w[i])
			{
				dis[rt][yy]=dis[rt][kk.id]+w[i];
				q.push(bh(yy,dis[rt][yy]));
			}
		}
	}
}
int main()
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	scanf("%lld%lld%lld",&n,&m,&k);
	for(long long i=1;i<=k;++i)
	{
		scanf("%lld",&wz[i]);
	}
	for(long long i=1;i<=m;++i)
	{
		long long x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		jia(x,y,z);
		jia(y,x,z);
	}
	for(long long i=1;i<=k;++i)
	{
		spfa(i);//预处理k个城镇到各点的距离
	}
	long long ans=0x3f3f3f3f;
	for(long long i=1;i<=n;++i)//枚举选的农场
	{
		long long flag=0;
		for(long long j=1;j<=k;++j) if(i==wz[j]) {flag=1;break;}
		if(flag) continue;//城镇不能选，不是吗？
		memset(f,0x3f3f3f,sizeof(f));
		for(long long j=1;j<=k;++j)
		{
			f[1<<(j-1)][j]=dis[j][i];//见上初始时
		}
		for(long long j=1;j<(1<<k);++j)
		{
			for(long long pp=1;pp<=k;++pp)//枚举当前所在的城镇
			if(j&(1<<(pp-1)))
			{
				for(long long qq=1;qq<=k;++qq)//枚举之前所在的城镇
				if(pp!=qq&&(j&(1<<(qq-1))))
				{
					f[j][pp]=min(f[j][pp],f[j^(1<<(pp-1))][qq]+dis[qq][wz[pp]]);//转移
				}
			}
		}
		for(long long j=1;j<=k;++j)//枚举最后所在的城镇
		{
			ans=min(ans,f[(1<<k)-1][j]+dis[j][i]);//取最小值
		}
	}
	printf("%lld",ans);
	return 0;
}

完结撒花。。。