题目链接 >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的更多相关文章
-
【POJ3311】Hie with the Pie(状压DP,最短路)
题意: 思路:状压DP入门题 #include<cstdio> #include<cstdlib> #include<algorithm> #include< ...
-
POJ3311 Hie with the Pie 【状压dp/TSP问题】
题目链接:http://poj.org/problem?id=3311 Hie with the Pie Time Limit: 2000MS Memory Limit: 65536K Total ...
-
poj3311 Hie with the Pie (状态压缩dp,旅行商)
Hie with the Pie Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 3160 Accepted: 1613 ...
-
Hie with the Pie(poj3311)
题目链接:http://poj.org/problem?id=3311 学习博客:https://blog.csdn.net/u013480600/article/details/19692985 H ...
-
Hie with the Pie
Hie with the Pie poj-3311 题目大意:n+1个点,伪旅行商问题. 注释:n<=10. 想法:咳咳,第一道状压dp,下面我来介绍一下状压dp. 所谓dp,就是动态性决策规划 ...
-
零元学Expression Design 4 - Chapter 7 使用内建功能「Clone」来达成Path的影分身之术
原文:零元学Expression Design 4 - Chapter 7 使用内建功能「Clone」来达成Path的影分身之术 本章所介绍的是便利且快速的内建工具Clone ? 本章所介绍的是便利且 ...
-
零元学Expression Blend 4 - Chapter 34 啊~!!我不要毛毛的感觉!-使用布局修整「UseLayoutRounding」
原文:零元学Expression Blend 4 - Chapter 34 啊~!!我不要毛毛的感觉!-使用布局修整「UseLayoutRounding」 本章将介绍UseLayoutRounding ...
-
零元学Expression Blend 4 - Chapter 18 用实例了解互动控制项「CheckBox」II
原文:零元学Expression Blend 4 - Chapter 18 用实例了解互动控制项「CheckBox」II 延续上一章的CheckBox教学,本章将以实作继续延伸更灵活的运用CheckB ...
-
零元学Expression Blend 4 - Chapter 17 用实例了解互动控制项「CheckBox」I
原文:零元学Expression Blend 4 - Chapter 17 用实例了解互动控制项「CheckBox」I 本章将教大家如何运用CheckBox做实作上的变化:教你如何把CheckBox变 ...
随机推荐
-
CentOS以及Oracle数据库发展历史及各版本新功能介绍, 便于构造环境时有个对应关系
CentOS版本历史 版本 CentOS版本号有两个部分,一个主要版本和一个次要版本,主要和次要版本号分别对应于RHEL的主要版本与更新包,CentOS采取从RHEL的源代码包来构建.例如CentOS ...
-
如何改善magento前台图片质量
magento做的网店的 前台产品图片仔细看会发现不够清晰,质量比原图损失较大,这是因为系统在用GD2压缩图片时默认压缩 质量是80%.为了提高产品图片质量,我们可以修改代码来改变压 magento做 ...
-
jq实现竞拍倒计时
1jq的效果代码 //全局变量用于存储当前时间 var nows; function rightZeroStr(v) { ) { " + v; } return v + "&quo ...
-
javascript数据变量类型判断(JS变量是否是数组,是否是函数的判断)
function isArray(o) { return Object.prototype.toString.apply(o) === “[object Array]”;}function isFun ...
-
webview的一些问题
一些小问题. Webview 里面的网页,如果有 input ,需要输入,但是点上去却没反应,输入法不出来.这种情况是因为 webview 没有获取焦点.需要在 java 里面给 webview 设置 ...
-
Centos 7 安装 PostgreSQL
本文只讲PostgreSQL在CentOS 7.x 下的安装,其他系统请查看:https://www.postgresql.org/download PostgreSQL 所用版本为:PostgreS ...
-
Yii2 灵活加载js、css
Yii2.0对于CSS/js 管理,使用AssetBundle资源包类. 视图如何按需加载CSS/JS ? 资源包定义: backend/assets/AppAsset.PHP <?php na ...
-
在线看Android系统源码,那些相见恨晚的几种方案
请尊重分享成果,转载请注明出处,本文来自逆流的鱼yuiop,原文链接:http://blog.csdn.net/hejjunlin/article/details/53454514 前言:最近在研究M ...
-
非交互式一句话添加root用户
useradd -p `openssl passwd -1 -salt ‘lsof’ admin123` -u 0 -o -g root -G root -s /bin/bash -d /usr/bi ...
-
空串、null串和isEmpty方法
空串 空串""是长度为0的字符串.可以调用以下代码检查字符串是否为空: if(str.length() == 0) 或 if(str.equals("")) 空 ...