「POJ3311」Hie with the Pie

时间:2022-10-06 08:59:15

题目链接 >http://poj.org/problem?id=3311<

题意:从0出发,经过所有点(点可以重复走)后回到0点,问最短路

思路分析:

  这题和普通的最短路不太一样,因为题目要求每个点都要走一遍。

  因此我们选择状压。

  用SPFA直接开始做,f[i][status]表示到达点i时,状态为status时的最短路,答案就是f[0][(1<<(n+1))-1]

  更新也和SPFA一模一样

/*By QiXingzhi*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int N = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();
return x * w;
}
struct Pizza{
int u, sta;
};
int n;
int G[N][N],d[N][];
queue <Pizza> q;
inline void Debug(int status){
int tmp[];
memset(tmp,,sizeof(tmp));
int tot = ;
while(status > ){
tmp[++tot] = status % ;
status /= ;
}
for(int i = tot; i > ; --i){
printf("%d",tmp[i]);
}
}
inline void SPFA(){
// printf("u = %d status = ",u); Debug(status); printf(" d = %d\n",d[u][status]);
memset(d,0x3f,sizeof(d));
d[][] = ;
Pizza tmp; tmp.u = , tmp.sta = ;
q.push(tmp);
int u,status;
while(!q.empty()){
Pizza __t = q.front();
Pizza __next;
u = __t.u;
status = __t.sta;
q.pop();
for(int i = ; i <= n; ++i){
if(G[u][i] == ) continue;
if(d[u][status] + G[u][i] < d[i][status ^ ( << (i))]){
d[i][status ^ ( << (i))] = d[u][status] + G[u][i];
__next.u = i;
__next.sta = status ^ ( << (i));
q.push(__next);
}
}
} }
int main(){
// freopen(".in","r",stdin);
// freopen("debug.txt","w",stdout);
while(){
n = r;
if(n == ) break;
for(int i = ; i <= n; ++i){
for(int j = ; j <= n; ++j){
G[i][j] = r;
}
}
SPFA();
printf("%d\n", d[][(<<(n+))-]);
}
return ;
}

「POJ3311」Hie with the Pie的更多相关文章

  1. 【POJ3311】Hie with the Pie(状压DP,最短路)

    题意: 思路:状压DP入门题 #include<cstdio> #include<cstdlib> #include<algorithm> #include< ...

  2. POJ3311 Hie with the Pie 【状压dp&sol;TSP问题】

    题目链接:http://poj.org/problem?id=3311 Hie with the Pie Time Limit: 2000MS   Memory Limit: 65536K Total ...

  3. poj3311 Hie with the Pie &lpar;状态压缩dp,旅行商&rpar;

    Hie with the Pie Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 3160   Accepted: 1613 ...

  4. Hie with the Pie(poj3311)

    题目链接:http://poj.org/problem?id=3311 学习博客:https://blog.csdn.net/u013480600/article/details/19692985 H ...

  5. Hie with the Pie

    Hie with the Pie poj-3311 题目大意:n+1个点,伪旅行商问题. 注释:n<=10. 想法:咳咳,第一道状压dp,下面我来介绍一下状压dp. 所谓dp,就是动态性决策规划 ...

  6. 零元学Expression Design 4 - Chapter 7 使用内建功能「Clone」来达成Path的影分身之术

    原文:零元学Expression Design 4 - Chapter 7 使用内建功能「Clone」来达成Path的影分身之术 本章所介绍的是便利且快速的内建工具Clone ? 本章所介绍的是便利且 ...

  7. 零元学Expression Blend 4 - Chapter 34 啊~&excl;&excl;我不要毛毛的感觉&excl;-使用布局修整「UseLayoutRounding」

    原文:零元学Expression Blend 4 - Chapter 34 啊~!!我不要毛毛的感觉!-使用布局修整「UseLayoutRounding」 本章将介绍UseLayoutRounding ...

  8. 零元学Expression Blend 4 - Chapter 18 用实例了解互动控制项「CheckBox」II

    原文:零元学Expression Blend 4 - Chapter 18 用实例了解互动控制项「CheckBox」II 延续上一章的CheckBox教学,本章将以实作继续延伸更灵活的运用CheckB ...

  9. 零元学Expression Blend 4 - Chapter 17 用实例了解互动控制项「CheckBox」I

    原文:零元学Expression Blend 4 - Chapter 17 用实例了解互动控制项「CheckBox」I 本章将教大家如何运用CheckBox做实作上的变化:教你如何把CheckBox变 ...

随机推荐

  1. CentOS以及Oracle数据库发展历史及各版本新功能介绍&comma; 便于构造环境时有个对应关系

    CentOS版本历史 版本 CentOS版本号有两个部分,一个主要版本和一个次要版本,主要和次要版本号分别对应于RHEL的主要版本与更新包,CentOS采取从RHEL的源代码包来构建.例如CentOS ...

  2. 如何改善magento前台图片质量

    magento做的网店的 前台产品图片仔细看会发现不够清晰,质量比原图损失较大,这是因为系统在用GD2压缩图片时默认压缩 质量是80%.为了提高产品图片质量,我们可以修改代码来改变压 magento做 ...

  3. jq实现竞拍倒计时

    1jq的效果代码 //全局变量用于存储当前时间 var nows; function rightZeroStr(v) { ) { " + v; } return v + "&quo ...

  4. javascript数据变量类型判断&lpar;JS变量是否是数组,是否是函数的判断&rpar;

    function isArray(o) { return Object.prototype.toString.apply(o) === “[object Array]”;}function isFun ...

  5. webview的一些问题

    一些小问题. Webview 里面的网页,如果有 input ,需要输入,但是点上去却没反应,输入法不出来.这种情况是因为 webview 没有获取焦点.需要在 java 里面给 webview 设置 ...

  6. Centos 7 安装 PostgreSQL

    本文只讲PostgreSQL在CentOS 7.x 下的安装,其他系统请查看:https://www.postgresql.org/download PostgreSQL 所用版本为:PostgreS ...

  7. Yii2 灵活加载js、css

    Yii2.0对于CSS/js 管理,使用AssetBundle资源包类. 视图如何按需加载CSS/JS ? 资源包定义: backend/assets/AppAsset.PHP <?php na ...

  8. 在线看Android系统源码,那些相见恨晚的几种方案

    请尊重分享成果,转载请注明出处,本文来自逆流的鱼yuiop,原文链接:http://blog.csdn.net/hejjunlin/article/details/53454514 前言:最近在研究M ...

  9. 非交互式一句话添加root用户

    useradd -p `openssl passwd -1 -salt ‘lsof’ admin123` -u 0 -o -g root -G root -s /bin/bash -d /usr/bi ...

  10. 空串、null串和isEmpty方法

    空串 空串""是长度为0的字符串.可以调用以下代码检查字符串是否为空: if(str.length() == 0) 或 if(str.equals("")) 空 ...