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个地区，在2号地区有能量块，飘飘乎居士行走的路线如下
1->3->2->1->3
行走的总路程为7，也就是最后的答案。
题解：
裸状压。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define max(a, b) a > b ? a : b
#define min(a, b) a < b ? a : b inline void read(int &x)
{
x = ;char ch = getchar();char c = ch;
while(ch > '' || ch < '')c = ch, ch = getchar();
while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();
if(c == '-')x = -x;
} const int MAXN = + ;
const int MAXP = + ; int g[MAXN][MAXN], n, p, dir[MAXP], ok1, ok2;
int f[MAXN][ << MAXP]; int main()
{
memset(f, 0X3f, sizeof(f));
read(n);
for(register int i = ;i <= n;++ i)
for(register int j = ;j <= n;++ j)
read(g[i][j]);
for(register int k = ;k <= n;++ k)
for(register int i = ;i <= n;++ i)
for(register int j = ;j <= n;++ j)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
read(p);
for(register int i = ;i <= p;++ i)
{
read(dir[i]);
if(dir[i] == ) ok1 = true;
else if(dir[i] == n) ok2= true;
}
if(!ok1) dir[++ p] = ;
if(!ok2) dir[++ p] = n; std::sort(dir + , dir + + p);
f[][] = ;
//f[i][S]表示从1出发走到点i，取到了S的能量块的最短路径
register int M = << p, now, tmp;
for(register int S = ;S < M;++ S)
{
for(register int i = ;i <= p;++ i)
{
if(!(S & ( << (i - ))))continue;
now = dir[i];
for(register int j = ;j <= p;++ j)
{
if(i == j)continue;
if(!(S & ( << (j - ))))continue;
tmp = dir[j];
f[now][S] = min(f[now][S], f[tmp][S ^ ( << (i - ))] + g[tmp][now]);
}
}
}
printf("%d", f[n][M - ]);
return ;
}
tyvj1288