Tyvj P1288 飘飘乎居士取能量块

本文主要是介绍Tyvj P1288 飘飘乎居士取能量块，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

背景
9月21日，pink生日；9月22日，lina生日；9月23日，轮到到飘飘乎居士（狂欢吧，(^__^) 嘻嘻……）。
描述
9月21日，今天是pink的生日，飘飘乎居士当然要去别人的领土大闹一番啦！
为了收集更多的能量到pink家大闹，飘飘乎居士准备从后花园中取出自己多年积攒的p个能量块。后花园一共被划分n个地区，能量块被分散在里面，现在飘飘乎居士拿出地图，发现自己站在1的地方，而他要做的就是用最短的路程把所有的能量块取出，并且最后走到位于n的出口处，而飘飘乎居士一直是个懒人，他想知道最少要走多少路程才能够取到所有的能量块，并且走到出口
输入格式
第一行一个正整数n，表示花园被划分成了n个地区
接下来一个n*n的矩阵，代表个点之间的相互距离，数据保证从i走到i没有路程
在下来一个整数p，表示一共有p个能量块
接下来一行，表示各个能量块的位置，数据保证1和n没有能量块,且每个地区最多一个能量块
对于所有的数据 0< n<=100 0<=P<=10 任意两点的距离为一个小于1000的正整数
输出格式
一个数，飘飘乎居士所要行走的最小距离
测试样例1
输入
3
0 10 1
3 0 5
1 2 0
1
2
输出
7
备注
花园被分为3个地区，在2号地区有能量块，飘飘乎居士行走的路线如下
1->3->2->1->3
行走的总路程为7，也就是最后的答案。

Floyd预处理出每两点之间的最短路
然后问题就转化为了关于必须走的点集的哈密顿路径问题
可以搜索点集的顺序（排列），或使用状态压缩DP
第一次因为数组开小了，wa了
感谢yny神犇指导。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,p,ans=1e7,sum,c[15],f[101][101];
int main()
{scanf("%d",&n);memset(f,0x3f,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]=min(f[i][j],f[i][k]+f[k][j]);scanf("%d",&p);for(int i=1;i<=p;i++)scanf("%d",&c[i]);c[0]=1;c[p+1]=n;sort(c+1,c+p+1);while(1){sum=0;for(int i=1;i<=p+1;i++)sum+=f[c[i-1]][c[i]];if(ans>sum)ans=sum;if(!next_permutation(c+1,c+p+1))break;}printf("%d\n",ans);return 0;
}