首页 > 代码库 > HDU 5067
HDU 5067
http://acm.hdu.edu.cn/showproblem.php?pid=5067
规定起点和终点的tsp问题,解法依然是状态压缩dp,在初始化和计算答案的时候略做改动即可
#include <iostream>#include <cstdio>#include <map>#include <cstring>using namespace std ;const int INF=0xfffffff ;int n,m ;int M[55][55] ;int dis[15][15] ;int dp[1<<15][15] ;int ABS(int x){return x>0?x:-x ;}struct point{ int x,y ;}p[15] ;int cal(point a,point b){ return ABS(a.x-b.x)+ABS(a.y-b.y) ;}int main(){ while(~scanf("%d%d",&n,&m)) { for(int i=0 ;i<n ;i++) { for(int j=0 ;j<m ;j++) { scanf("%d",&M[i][j]) ; } } int cnt=0 ; for(int i=0 ;i<n ;i++) { for(int j=0 ;j<m ;j++) { if(i==0 && j==0)continue ; if(M[i][j]) { p[cnt].x=i ; p[cnt++].y=j ; } } } for(int i=0 ;i<15 ;i++) for(int j=0 ;j<15 ;j++) dis[i][j]=INF ; for(int i=0 ;i<cnt ;i++) { for(int j=0 ;j<cnt ;j++) { if(i==j) { dis[i][j]=0 ; continue ; } dis[i][j]=cal(p[i],p[j]) ; } } point s ; s.x=0 ;s.y=0 ; for(int i=0 ;i<(1<<15) ;i++) for(int j=0 ;j<15 ;j++) dp[i][j]=INF ; for(int i=0 ;i<cnt ;i++) { dp[1<<i][i]=cal(s,p[i]) ; } for(int i=0 ;i<(1<<cnt) ;i++) { for(int j=0 ;j<cnt ;j++) { if(i&(1<<j)) { for(int k=0 ;k<cnt ;k++) { if(dis[k][j]==INF || !(i&(1<<k)))continue ; dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+dis[k][j]) ; } } } } int ans=INF ; for(int i=0 ;i<cnt ;i++) { ans=min(ans,dp[(1<<cnt)-1][i]+cal(p[i],s)) ; } if(ans==INF) { puts("0") ; continue ; } printf("%d\n",ans) ; } return 0 ;}
HDU 5067
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。