POJ 3311 Hie with the Pie (BFS+最短路+状态压缩)

题意:类似于TSP问题,只是每个点可以走多次,求回到起点的最短距离(起点为点0)。

分析:状态压缩,先预处理各点之间的最短路,然后sum【i】【buff】表示在i点,状态为buff时所耗时。。。。。。。

所以把10 * 1024 种状态来一遍,取sum【0】【(1<<n)-1】的最小值

只是把状态压缩DP改成bfs+状态压缩了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#define INF 0x7FFFFFFF
using namespace std; int dist[11][11],sum[11][1 << 10];
struct node {
int x,buff;
} q[55555];
int head,tail,n,ans; void floyd() {
for(int i=0; i<=n; i++) {
for(int j=0; j<=n; j++) {
for(int k=0; k<=n; k++) {
if(dist[j][i] + dist[i][k] < dist[j][k]) dist[j][k] = dist[j][i] + dist[i][k];
}
}
}
} void bfs() {
ans = INF;
memset(sum,0,sizeof(sum));
head = 0;
tail = 0;
q[head].x = 0;
q[head++].buff = 0;
while(head != tail) {
node t = q[tail ++];
node tt;
if(t.x == 0 && t.buff == (1 << n) - 1) {
ans = min(ans,sum[t.x][t.buff]);
}
for(int i=0; i<=n; i++) {
if(t.x == i) continue;
if(i != 0) {
if(t.buff & (1 << (i-1))) tt.buff = t.buff;
else tt.buff = t.buff + (1 << (i-1));
} else tt.buff = t.buff;
//如果该点该状态已经访问过,而这次如果没有更优解,则剪了
if(sum[i][tt.buff] != 0 && sum[i][tt.buff] > sum[t.x][t.buff] + dist[t.x][i]) {
sum[i][tt.buff] = sum[t.x][t.buff] + dist[t.x][i];
tt.x = i;
q[head++] = tt;
//未访问则老样子
} else if(sum[i][tt.buff] == 0) {
sum[i][tt.buff] = sum[t.x][t.buff] + dist[t.x][i];
tt.x = i;
q[head ++] = tt;
}
}
}
}
int main() {
while(scanf("%d",&n) && n) {
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++) {
scanf("%d",&dist[i][j]);
}
floyd();
bfs();
printf("%d\n",ans);
}
return 0;
}
上一篇:MS10-070 ASP.NET Padding Oracle信息泄露漏洞项目测试


下一篇:Padding Oracle 和 CBC字节翻转攻击学习