首页 > 代码库 > tyvjP1288 飘飘乎居士取能量块
tyvjP1288 飘飘乎居士取能量块
P1288 飘飘乎居士取能量块
时间: 1000ms / 空间: 131072KiB / Java类名: Main
背景
9月21日，pink生日；9月22日，lina生日；9月23日，轮到到飘飘乎居士（狂欢吧，(*^__^*) 嘻嘻……）。
描述
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
输入
3
0 10 1
3 0 5
1 2 0
1
2
输出
7
备注
花园被分为3个地区，在2号地区有能量块，飘飘乎居士行走的路线如下
1->3->2->1->3
行走的总路程为7，也就是最后的答案。
题解：
裸状压。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 #define max(a, b) a > b ? a : b 7 #define min(a, b) a < b ? a : b 8 9 inline void read(int &x)10 {11 x = 0;char ch = getchar();char c = ch;12 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();13 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar();14 if(c == ‘-‘)x = -x;15 }16 17 const int MAXN = 100 + 10;18 const int MAXP = 10 + 5;19 20 int g[MAXN][MAXN], n, p, dir[MAXP], ok1, ok2;21 int f[MAXN][1 << MAXP];22 23 int main()24 {25 memset(f, 0X3f, sizeof(f));26 read(n);27 for(register int i = 1;i <= n;++ i)28 for(register int j = 1;j <= n;++ j)29 read(g[i][j]);30 for(register int k = 1;k <= n;++ k)31 for(register int i = 1;i <= n;++ i)32 for(register int j = 1;j <= n;++ j)33 g[i][j] = min(g[i][j], g[i][k] + g[k][j]);34 read(p);35 for(register int i = 1;i <= p;++ i)36 {37 read(dir[i]);38 if(dir[i] == 1) ok1 = true;39 else if(dir[i] == n) ok2= true;40 }41 if(!ok1) dir[++ p] = 1;42 if(!ok2) dir[++ p] = n;43 44 std::sort(dir + 1, dir + 1 + p);45 f[1][1] = 0;46 //f[i][S]表示从1出发走到点i，取到了S的能量块的最短路径47 register int M = 1 << p, now, tmp;48 for(register int S = 1;S < M;++ S)49 {50 for(register int i = 1;i <= p;++ i)51 {52 if(!(S & (1 << (i - 1))))continue;53 now = dir[i];54 for(register int j = 1;j <= p;++ j)55 {56 if(i == j)continue;57 if(!(S & (1 << (j - 1))))continue;58 tmp = dir[j];59 f[now][S] = min(f[now][S], f[tmp][S ^ (1 << (i - 1))] + g[tmp][now]);60 }61 }62 }63 printf("%d", f[n][M - 1]);64 return 0;65 }
tyvjP1288 飘飘乎居士取能量块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。