「USACO12FEB」Relocation

题意：FJ 决定搬家，重新建设农场，以便最小化他每天的行程。FJ搬往的区域有 $N(1\leq N\leq 10000)$ 个城镇，共有 $M (1 \leq M\leq 50000)$ 条双向道路连接某些城镇，所有城镇都能找到互通路线。有 $K (1\leq K\leq 5)$ 个城镇建有市场，FJ每天离开新农场后，都要光顾这 $K$ 个城镇，并返回农场。FJ希望建设农场的城镇不包含市场。请帮助FJ选择最佳城镇建设农场，使得他每天的行程最小。

最短路，于是 Dijkstra 算法；

由于要到 $K$ 个城镇，所以我们以这 $K$ 个城镇为起点执行 $K$ 次 Dijkstra 算法，然后就可以得到从这 $K$ 个城镇出发的最短路。

但是我们要从一个点出发连续光顾 $K$ 个城镇，由于 $(1\leq K\leq 5)$，我们可以直接暴力枚举走这 $K$ 个城镇的顺序，即全排列。

对于每个顺序，我们又枚举其他不是城镇的点作为农场点，很明显，连续走 $K$ 个城镇的距离时，从 $1$ 号城镇到 $K$ 号城镇的路是不变的，所以我们可以先预处理出这部分距离，这样枚举时就只用把农场点分别到 $1$ 和 $K$ 点的距离和这部分距离加上即可，最后求个最小值，得到答案。

注意在存储最短路数组时，我们第一维存的是这 $K$ 个城镇对应的下标，而不是它们的编号，所以我们要同时开个数组记录编号对应的下标(即代码中的 p 数组)，这样在求距离时方便处理。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,k;
int head[110101],cnt;
int dis[6][100101],ex[100101],p[101010];
int s[101010],ans=2e9,a[101010];
bool book[101010];
struct node
{
	int next;
	int to;
	int num;
}e[200101];
priority_queue< pair<int,int> > q;
void add(int from,int to,int num)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	e[cnt].num=num;
	head[from]=cnt;
}
void dijkstra(int x)
{
	memset(dis[x],0x3f,sizeof(dis[x]));
	memset(ex,0,sizeof(ex));
	dis[x][s[x]]=0;
	q.push(make_pair(0,s[x]));
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(ex[u])
			continue;
		ex[u]=1;
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(dis[x][v]>dis[x][u]+e[i].num)
			{
				dis[x][v]=dis[x][u]+e[i].num;
				q.push(make_pair(-dis[x][v],v));
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&s[i]);
		p[s[i]]=i;
		book[s[i]]=1;
		a[i]=s[i];
	}
	sort(a+1,a+k+1);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	for(int i=1;i<=k;i++)
		dijkstra(i);
	do
	{
		int sum=0;
		for(int i=1;i<k;i++)
			sum+=dis[p[a[i]]][a[i+1]];//预处理
		for(int i=1;i<=n;i++)
		{
			if(book[i])
				continue;
			ans=min(ans,sum+dis[p[a[1]]][i]+dis[p[a[k]]][i]);//求最小
		}
	}while(next_permutation(a+1,a+k+1));
	printf("%d",ans);
	return 0;
}