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

分析:

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

n 100 n\leq100 n100

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

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

p 10 p\leq10 p10

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

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

此函数比如 n e x t next next_ p e r m u t a t i o n ( t + 1 , t + 1 + p ) permutation(t+1,t+1+p) permutation(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~
}