HDU3001 Travelling

http://acm.hdu.edu.cn/showproblem.php?pid=3001

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.

Input

There are several test cases,the first line is two intergers n(1<=n<=10) and m,which means he needs to visit n cities and there are m roads he can choose,then m lines follow,each line will include three intergers a,b and c(1<=a,b<=n),means there is a road between a and b and the cost is of course c.Input to the End Of File.

Output

Output the minimum fee that he should pay,or -1 if he can't find such a route.

 

题意:从任一点出发,走完n个点,每个点最多访问2次,求最短总路程。

思路:每个点只能访问1次就是经典tsp问题,不限制访问次数的话floyd预处理一下,而这道题是限制最多两次,那么用三进制状压dp。

不能直接用位运算了,得用数组模拟。

求出3^i,i∈[0,10],最大是3^10=59049。0~3^10-1就可以表示10位3进制数。

s的第i位2变为1,1变为0,就是s-fac(i)

因为起点固定而终点不固定,所以状态设计必须是以...为起点的。

设f(i,s):现在在i,访问情况压位在s中,对应的最小总路程。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f

int n,m,d[15][15],f[15][60005];
int fac[15],num[60005][15];

void init()
{
	int x,y;
	fac[0]=1;
	for(int i=1;i<=10;i++)fac[i]=fac[i-1]*3;
	for(int s=0;s<fac[10];s++)
	{
		int i=s;
		for(int j=0;j<10;j++)num[s][j]=i%3,i/=3;
	}
}

void debug()
{
	for(int s=0;s<fac[n];s++)
	{
		for(int v=0;v<n;v++)printf("position:%d,bit:%d,f:%d\n",s,f[v][s]);
	}
}

int dp()
{
	memset(f,INF,sizeof(f));
	int minn=INF;
	for(int i=0;i<n;i++)f[i][fac[i]]=0;//搞清楚两维不要反了 
	for(int s=0;s<fac[n];s++)
	{
		bool ok=1;
		for(int v=0;v<n;v++)
		{
			if(num[s][v]==0){ok=0;continue;}
			for(int u=0;u<n;u++)			//u->v 
			{
				if(num[s-fac[v]][u]==0)continue;
				f[v][s]=min(f[v][s],f[u][s-fac[v]]+d[u][v]);
			}
		}
		if(ok)for(int i=0;i<n;i++)minn=min(minn,f[i][s]);
	}
	return minn;
}

int main()
{
//	freopen("input.in","r",stdin);
	init();
	int x,y,z;
	while(cin>>n>>m)
	{
		memset(d,INF,sizeof(d));
		while(m--)
		{
			cin>>x>>y>>z;
			x--;y--;	//把1~n变成0~n-1 
			d[y][x]=d[x][y]=min(d[x][y],z);
		}
		int minn=dp();
		if(minn!=INF)cout<<minn<<endl;
		else cout<<-1<<endl;
	}
//	debug();
	return 0;
}

 

 

 

 

 

全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
点赞 评论 收藏
分享
咦哟,从去年八月份开始长跑,两处实习转正都失败了,风雨飘摇,终于拿到offer了更新一下面试记录:秋招:多部门反复面试然后挂掉然后复活,具体问了啥已经忘了,只是被反复煎炸,直至焦香😋春招:base北京抖音hr打来电话说再次复活,准备面试,gogogo北京抖音一面:六道笔试题:1.promise顺序2.定义域问题3.flat展开4.并发请求5.岛屿数量算法(力扣)深度,广度都写6.忘记了,好像也是算法,难度中等其他问题多是框架底层设计,实习项目重难点~~~秒过😇北京抖音二面:三道笔试题:(为什么只有三道是因为第三道没做出来,卡住了)1.中等难度算法(忘记啥题了,应该是个数组的)2.认识js的继承本质(手写继承模式,深入js的面相对象开发)3.手写vue的响应式(卡在了watch,导致挂掉)---后知后觉是我的注册副作用函数写得有问题,有点紧张了其他题目多是项目拷打,项目亮点,对实习项目的贡献~~~第二天,挂,but立马复活转战深圳客服当天约面深圳客服一面:六道笔试题,由于面过太多次字节,面试官叫我直接写,不用讲,快些写完😋,具体都是些继承,深拷贝(注意对数组对象分开处理,深层次对象,循环引用),加中等难度算法题~~~秒过深圳客服二面:口诉八股大战:大概囊括网络,浏览器渲染原理,动画优化,时间循环,任务队列等等(你能想到的简单八股通通拉出来鞭尸😋)算法题:笔试题6道:1:找出数组内重复的数,arr[0]-arr[n]内的数大小为[1-n],例如[1,2,2,3,3]返回[2,3],要求o(n),且不使用任何额外空间(做到了o(n),空间方面欠佳,给面试官说进入下一题,做不来了)2:原滋原味的继承(所以继承真滴很重要)3:力扣股票购买时机难度中等其他滴也忘记了,因为拿到offer后鼠鼠一下子就落地了,脑子自动过滤掉可能会攻击鼠鼠的记忆😷~~~秒过深圳客服三面:项目大战参与战斗的人员有:成员1:表单封装及其底层原理,使用成本的优化,声明式表单成员2:公司内部库生命周期管理成员3:第三方库和内部库冲突如何源码断点调试并打补丁解决成员4:埋点的艺术成员5:线上项目捷报频传如何查出内鬼成员6:大文件分片的风流趣事成员7:设计模式对对碰成员8:我构建hooks应对经理的新增的小需求的故事可能项目回答的比较流利,笔试题3道,都很简单,相信大家应该都可以手拿把掐😇~~~过过过无hr面后续煎熬等待几天直接hr打电话发offer了,希望大家也可以拿到自己心仪的offer
法力无边年:牛哇,你真是准备得充分,我对你没有嫉妒,都是实打实付出
查看19道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务