题目：https://www.luogu.org/problemnew/show/P1690
分析：
这道题就是一道最短路的题目，因为看到数据范围：
n≤100n\leq100n≤100
所以考虑使用FloydFloydFloyd
我们先用O(n3)O(n^3)O(n3)的时间复杂度来跑一遍FloydFloydFloyd,然后考虑每个藏宝点，发现藏宝点p的范围：
p≤10p\leq10p≤10
我们可以考虑所有情况的穷举，所以说是一个数列的全排列，最多只需要枚举10!=3628800种情况即可。
推荐使用nextnextnext_permutation()permutation()permutation()函数.
此函数比如nextnextnext_permutation(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~
}
转载于:https://www.cnblogs.com/vercont/p/10210057.html
相关资源：洛谷P1015回文数C 解
