1698: 送外卖
时间限制: 1 Sec 内存限制: 128 MB提交: 123 解决: 28
[提交][状态][讨论版]
题目描述
在美团和饿了么大行其道的今天，囊中羞涩的小周和小美，也随大流加入了配送员的行列。每天下课后，他们都去堕落街帮北京烤鸭店送外卖。
过了好些日子，小周发现每次送外卖，小美总比自己先回来，就算自己拼命跑啊跑，也总是比她慢，明明小美也是和自己一样，走着去送外卖的（等外卖的都饿死了╮(╯﹏╰)╭）。
小周忍不住问了小美这是怎么回事，小美说：“笨蛋，本小姐每次出去都选最短的路，肯定比你走远的路快啊！”
小周恍然大悟，深恨自己怎么没有早早想到这一点，不过亡羊补牢，为时未晚，立即决定效仿小美的做法。小周将店的位置标号为0，其他要送外卖的位置标号分别是1,2,3……然后又将各个标号之间的距离做了一张二维表A，其中A[0][i]代表从店家出发到第i个外卖点的距离，A[i][j](i!=0&&j!=0)表示第i个外卖点到第j个外卖点的距离。
小周每次都从店里出发，送完所有外卖之后，就从最后一个送完外卖的地点径直地回到店里，因为直接回去总是最近的，小周统计出来的表的确也是这样的。保证矩阵对称且主对角线上的元素都是0。
不过由于小周实在是太忙了，连计算最短路线的时间都没有，现在给你这张小周做好的表，请你帮小周确定一下最短的路线吧！
输入
第一行输入数据的组数T（1<=T<=50）。
对于每一组数据，第一行一个n（0 < n <= 9）,代表要送的外卖数量，然后一个(n+1)*(n+1)的矩阵A，代表小周的统计出来距离表，0 <= A[i][j] <= 500。
输出
对于每组数据，输出送完所有外卖并回到店里的最短的距离
样例输入
2 1 0 52 52 0 2 0 319 430 319 0 96 430 96 0
样例输出
104 845
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <string> #include <map> #include <cmath> #include <set> using namespace std; int n,Map[45][45],maxi; int status[25][1 << 10]; int DFS(int v,int S) { if(S==(maxi-2)) return Map[v][1]; if(status[v][S]) return status[v][S]; int M=99999999; for(int i=2; i<=n; i++) if(!(S&(1<<(i-1)))&&v!=i) { S|=(1<<(i-1)); M=min(M,DFS(i,S)+Map[v][i]); S&=(~(1<<(i-1))); } return status[v][S]=M; } int main() { //freopen("salesman.in","r",stdin); //freopen("salesman.out","w",stdout); int T; scanf("%d", &T); while(T--){ memset(status, 0, sizeof(status)); scanf("%d",&n); n++; maxi=(int)pow(2.0,n*1.0); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",&Map[i][j]); cout<<DFS(1,0)<<endl; } return 0; }