描述
9月21日，今天是pink的生日，飘飘乎居士当然要去别人的领土大闹一番啦！
为了收集更多的能量到pink家大闹，飘飘乎居士准备从后花园中取出自己多年积攒的p个能量块。后花园一共被划分n个地区，能量块被分散在里面，现在飘飘乎居士拿出地图，发现自己站在1的地方，而他要做的就是用最短的路程把所有的能量块取出，并且最后走到位于n的出口处，而飘飘乎居士一直是个懒人，他想知道最少要走多少路程才能够取到所有的能量块，并且走到出口
为了收集更多的能量到pink家大闹，飘飘乎居士准备从后花园中取出自己多年积攒的p个能量块。后花园一共被划分n个地区，能量块被分散在里面，现在飘飘乎居士拿出地图，发现自己站在1的地方，而他要做的就是用最短的路程把所有的能量块取出，并且最后走到位于n的出口处，而飘飘乎居士一直是个懒人，他想知道最少要走多少路程才能够取到所有的能量块，并且走到出口
输入格式
第一行一个正整数n，表示花园被划分成了n个地区
接下来一个n*n的矩阵，代表个点之间的相互距离，数据保证从i走到i没有路程
在下来一个整数p，表示一共有p个能量块
接下来一行，表示各个能量块的位置，数据保证1和n没有能量块,且每个地区最多一个能量块
对于所有的数据 0<n<=100 0<=P<=10 任意两点的距离为一个小于1000的正整数
接下来一个n*n的矩阵，代表个点之间的相互距离，数据保证从i走到i没有路程
在下来一个整数p，表示一共有p个能量块
接下来一行，表示各个能量块的位置，数据保证1和n没有能量块,且每个地区最多一个能量块
对于所有的数据 0<n<=100 0<=P<=10 任意两点的距离为一个小于1000的正整数
输出格式
一个数，飘飘乎居士所要行走的最小距离
//搜索 全排列 ↑题名字真诡异
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 int n,p; 7 int a[200][200];//邻接表 8 int pos[50];//能量块位置 9 int minda=9999999;//存储最优解 10 int sum=0; 11 12 13 int main(){ 14 // 15 scanf("%d",&n); 16 int i,j; 17 for(i=1;i<=n;i++) 18 for(j=1;j<=n;j++){ 19 scanf("%d",&a[i][j]);//读入 20 } 21 scanf("%d",&p); 22 for(i=1;i<=p;i++)scanf("%d",&pos[i]);//读入能量块位置 23 //floyd算法求最短距离 24 int k; 25 for(k=1;k<=n;k++) 26 for(i=1;i<=n;i++) 27 for(j=1;j<=n;j++) 28 if(a[i][j]>a[i][k]+a[k][j]) 29 a[i][j]=a[i][k]+a[k][j]; 30 //以上 31 pos[0]=1; 32 sort(pos+1,pos+p+1);//从小到大排序能量块位置，很神奇，加了这句话就AC 33 //后面函数可能不生效（p不够大时），所以先算一遍 34 sum=0; 35 for(i=1;i<=p;i++){ 36 sum+=a[pos[i-1]][pos[i]]; 37 // 38 // printf("%d + %d c:%d ",pos[i-1],pos[i],a[pos[i-1]][pos[i]]); 39 //测试输出用 40 } 41 sum+=a[pos[p]][n]; 42 if(minda>sum)minda=sum; 43 // 44 while(next_permutation(pos+1,pos+p+1)){//神奇的函数，作用是求数组全排列 45 sum=0; 46 for(i=1;i<=p;i++){ 47 sum+=a[pos[i-1]][pos[i]]; 48 // printf("%d ",pos[i]); 49 } 50 sum+=a[pos[p]][n]; 51 if(minda>sum)minda=sum; 52 } 53 cout<<minda; 54 return 0; 55 56 }
//完毕
总之就是要最短路径遍历1区，n区，每个能量块所在的区
（最短路径用floyd算法计算即可）
这个next_permutation函数可以求数组的全排列，简直好用，省了一番功夫
不用的话，还得自己写一个dfs求全排列
原本的思路是把所有能量块位置+1点+n点一起构成一个新的图，之后发现并不需要，直接在原有a图里做即可
↑另外构建新图可能会导致一些不必要的数据错位