洛谷P1690 贪婪的Copy 题解

题目：https://www.luogu.org/problemnew/show/P1690

分析：

这道题就是一道最短路的题目，因为看到数据范围：

$n \leq 100$

所以考虑使用 $F l o y d$

我们先用 $O (n^{3})$ 的时间复杂度来跑一遍 $F l o y d$ ,然后考虑每个藏宝点，发现藏宝点p的范围：

$p \leq 10$

我们可以考虑所有情况的穷举，所以说是一个数列的全排列，最多只需要枚举10!=3628800种情况即可。

推荐使用 $n e x t$ _ $p e r m u t a t i o n ()$ 函数.

此函数比如 $n e x t$ _ $p e r m u t a t i o n (t + 1, t + 1 + p)$ ;

就是生成一下t这个数列从下标1到下标p的下一个全排列。

借此我们即可枚举所有情况。

下面见代码

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int f[105][105],t[15];
int main()
{
	int n;
	scanf("%d",&n);
	memset(f,0x3f3f3f3f,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&f[i][j]);//存边
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				f[i][j]=fmin(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}//Floyd最短路模板，不再赘述
	int p;
	scanf("%d",&p);
	for(int i=1;i<=p;i++)
	{
		scanf("%d",&t[i]);
	}
	sort(t+1,t+p+1);//首先排列一下，为从小到大排序，以此为起点
	int tmp=1,ans=2147483647;
	while(tmp!=0)//还有就是那个函数如果已经用过这种排列，它的返回值就是0
	{
		tmp=next_permutation(t+1,t+1+p);
		int temp=f[1][t[1]]+f[t[p]][n];//挑出特殊的
        for(int i=1;i<p;i++)
            temp+=f[t[i]][t[i+1]];//循环
        ans=fmin(ans,temp);//找最短距离
	}
	printf("%d",ans);
	return 0;//bye~
}