刷题记录:HDU - 3001Travelling
admin
2024-03-18 04:39:58
0

传送门:VJudge

题目描述:

After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He 
has decided to visit n cities(he insists on seeing all the cities!And he does not mind which city being 
his start station because superman can bring him to any city at first but only once.), and of course 
there are m roads here,following a fee as usual.But Mr Acmer gets bored so easily that he doesn't 
want to visit a city more than twice!And he is so mean that he wants to minimize the total fee!He is 
lazy you see.So he turns to you for help.
输入:
2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10
输出:
100
90
7 

吐槽一下HDUoj,我当时没打!=EOF!=EOF!=EOF居然过不去,az…

对于这道题,是一道三进制状压dp题

对于每一个城市,我们都有三种状态可选,没有经过///经过一次///经过两次

对于上述的三种状态,我们可以将其转化三进制串进行存储,记为S

那么我们可以是用dp[S][u]来记录从u点开始走,完成S状态的最小步数dp[S][u]来记录从u点开始走,完成S状态的最小步数dp[S][u]来记录从u点开始走,完成S状态的最小步数

那么我们的当前结点显然可以由邻接点进行一个转移,当前结点完成S状态,显然可以由邻接点v完成{s}−u\{s\}-u{s}−u状态.这里可能有人会有疑问,我们的v可能完不成这个状态啊,因为u结点可能恰好是一个转接点,不用慌,对于这种情况,我们只要将初始数据赋值为inf就行,反正最后是取min的,如果没有这个合法状态返回的是inf,那么就没关系了

所以我们可以得出以下的状态转移方程:

dp[S][u]=min(dp[S][u],dp[S−u][v]+mp[u][[v])dp[S][u]=min(dp[S][u],dp[S-{u}][v]+mp[u][[v])dp[S][u]=min(dp[S][u],dp[S−u][v]+mp[u][[v])

其中mp[u][v]为两节点之间的边

到此为止这道题的大部分就已经结束了,接下来主要讲一下细节问题:

对于我们的初始状态,因为可以是从任何地方开始的,并且对于任何一个初始的城市开始,我们都可以预处理出它的初始状态(使用tri数组表示):

int tri[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049};

并且因为值三进制状压的话,我们就不能使用二进制状压中使用移位,&,|,之类的简单方式进行操作了,此时我们需要预处理出每一个状态的每一个位的数字:
使用init()init()init()函数直接进行预处理即可

void init() {for(int i=0;iint t=i;for(int j=1;j<=10;j++) {dig[i][j]=t%3;t/=3;if(t==0) break;}}
}

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
const int pow3max=59049;
int dp[pow3max+10][21];
int tri[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049};
int dig[pow3max][21];
void init() {for(int i=0;iint t=i;for(int j=1;j<=10;j++) {dig[i][j]=t%3;t/=3;if(t==0) break;}}
}
int n,m;
int mp[21][21];
int main() {init();while(scanf("%d%d",&n,&m)!=EOF) {memset(dp,0x3f,sizeof(dp));memset(mp,0x3f,sizeof(mp));int ans=inf;int a,b,c;for(int i=1;i<=m;i++) {a=read();b=read();c=read();mp[a][b]=mp[b][a]=min(mp[a][b],c);}for(int i=1;i<=n;i++) dp[tri[i]][i]=0;for(int S=0;Sint vis_all=1;for(int u=1;u<=n;u++) {if(dig[S][u]==0) {vis_all=0;continue;}for(int v=1;v<=n;v++) {if(dig[S][v]==0||v==u) continue;dp[S][u]=min(dp[S][u],dp[S-tri[u]][v]+mp[u][v]);}}if(vis_all==1) {for(int i=1;i<=n;i++) {ans=min(ans,dp[S][i]);}}}if(ans==inf) printf("-1\n");else printf("%d\n",ans);}return 0;
}

相关内容

热门资讯

怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...
安卓系统手写%怎样调出,具体实... 你有没有遇到过这种情况:在使用安卓手机的时候,突然想用手写输入法来记录一些灵感或者重要信息,可是怎么...
安卓手机重置 系统设置,轻松恢... 手机用久了是不是感觉卡顿得厉害?别急,今天就来教你怎么给安卓手机来个大变身——重置系统设置!想象你的...
win如何安装安卓系统,Win... 哇,你有没有想过,让你的Win系统也能玩转安卓应用?没错,就是那种在手机上轻松自如的安卓系统,现在也...
苹果qq和安卓系统,跨平台体验... 你有没有发现,现在手机市场上,苹果和安卓的较量可是越来越激烈了呢!咱们就来聊聊这个话题,看看苹果QQ...
显示最好的安卓系统,探索最新旗... 你有没有想过,为什么安卓系统那么受欢迎呢?它就像一个魔法盒子,里面装满了各种神奇的魔法。今天,就让我...
安卓app怎么降级系统,系统版... 你有没有发现,有时候安卓手机的系统更新后,新功能虽然炫酷,但老系统用起来更顺手呢?别急,今天就来教你...
雷军脱离安卓系统,引领科技变革... 你知道吗?最近科技圈可是炸开了锅,因为我们的雷军大大竟然宣布要脱离安卓系统,这可真是让人大跌眼镜啊!...
安卓系统自动开网络,安卓系统自... 你有没有发现,手机里的安卓系统有时候会自动开启网络连接,这可真是让人又爱又恨啊!有时候,你正专心致志...
安卓系统怎样控制后台,因为服务... 手机里的安卓系统是不是感觉越来越卡了?后台程序太多,不仅耗电还影响性能。别急,今天就来教你怎么巧妙地...
安卓系统打游戏推荐,一触即达! 你有没有发现,现在手机游戏越来越好玩了?不管是休闲小游戏还是大型MMORPG,都能在手机上畅玩。但是...