首页 > 代码库 > HDU 5067

HDU 5067

2024-07-28 00:44:32   220人阅读

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 ;}
View Code

 

HDU 5067


联系
我们