hdu 3001 Travelling (TSP问题 )

hdu 3001 Travelling (TSP问题 )

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Travelling

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3905    Accepted Submission(s): 1234




Problem Description
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.
 


Sample Input
   
   
2 1 1 2 100 3 2 1 2 40 2 3 50 3 3 1 2 3 1 3 4 2 3 10

 


Sample Output
   
   
100 90 7


DP+状态压缩:每一个点最多仅仅能经过2次,考虑用3进制存储状态;

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 12
#define M 59050
#define LL long long
const int inf=0x1f1f1f1f;  //注意初始化值
int tri[N]= {0,1,3,9,27,81,243,729,2187,6561,19683,59049};
int g[N][N];
int dig[M][N]; //dig[i][j]记录I状态下J点是否出现,出现几次
int dp[M][N]; //dp[s][j] 在状态s下,以j为终点的最短距离
void inti()     //求出每一个状态s相应的3进制位的信息
{
    int i,j,t;
    for(i=1;i<M;i++)
    {
        for(t=i,j=1;j<=10;j++)
        {
            dig[i][j]=t%3;          //求出该状态下到达每一个的城市次数
            t/=3;
            if(!t) break;
        }
    }
}
int main()
{
    int i,j,a,b,c;
    int n,m,s;
    inti();
    while(scanf("%d%d",&n,&m)!=-1)
    {
        memset(g,inf,sizeof(g));
        memset(dp,inf,sizeof(dp));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            g[a][b]=g[b][a]=min(c,g[a][b]);
        }
        for(i=1;i<=n;i++)      //起始状态。能够任一城市为起点。
            dp[tri[i]][i]=0;   //距离自然初始化为0
        int ans=inf;
        for(s=1;s<tri[n+1];s++)  //在s状态以i为终点时更新其它状态的值
        {
            int f=1;
            for(i=1;i<=n;i++)
            {
                if(dig[s][i]==0)     //推断当前状态S下,每一个城市是否都已到达
                    f=0;
                if(dp[s][i]==inf)
                    continue;
                for(j=1;j<=n;j++) //dp[s][i]状态到dp[s+tri[j]][j]状态
                {
                    if(g[i][j]==inf||i==j||dig[s][j]>=2)
                        continue;
                    int news=s+tri[j];
                    dp[news][j]=min(dp[news][j],dp[s][i]+g[i][j]);
                }
            }
            if(f)  
                for(i=1;i<=n;i++)
                ans=min(ans,dp[s][i]);
        }
        if(ans==inf)
            ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}

</pre><p></p><p></p><p><span style="font-size:18px; color:#33ccff">bfs+状态压缩:</span></p><p><span style="color:rgb(51,204,255); font-size:18px">開始时把每个点都入队,模拟3进制处理每个状态,最后+优化。

</span></p><p></p><pre code_snippet_id="479354" snippet_file_name="blog_20141004_2_7195338" name="code" class="cpp">#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<algorithm>#include<iostream>#include<queue>using namespace std;#define N 12#define LL long longconst int inf=0x3fffffff;int g[N][N];int n,m,ans;int mark[N][60000];struct node{ int x,t,s,cnt; //位置、时间、状态、个数 friend bool operator<(node a,node b) { return a.t>b.t; }};int gettmp(int x,int k) //得到X在3进制下的第K位是多少{ //推断该点是否经过了。经过了几次 int t; while(x) { t=x%3; k--; if(k==0) break; x/=3; } return k?0:t;}void inti() //初始化数组{ int i,j; for(i=1;i<=n;i++) { for(j=0;j<(int)pow(3,n);j++) mark[i][j]=inf; }}void bfs(){ int i; priority_queue<node>q; node cur,next; for(i=1;i<=n;i++) { cur.x=i; cur.s=pow(3,(i-1)); cur.t=0; cur.cnt=1; q.push(cur); mark[i][0]=0; } while(!q.empty()) { cur=q.top(); q.pop(); for(i=1;i<=n;i++) { if(g[cur.x][i]==inf) //此路不通 continue; next.cnt=cur.cnt; next.s=cur.s; next.t=cur.t+g[cur.x][i]; if(ans<next.t) //优化非常重要 continue; next.x=i; int t=gettmp(next.s,i); //该点经过了几次, if(t>=2) //经过2次后就不能走了 continue; next.s+=pow(3,(i-1)); //该点经过次数加一 if(t==0) //经过一个新景点 { next.cnt++; if(next.cnt==n) { ans=min(ans,next.t); continue; } } if(next.t<mark[i][next.s]) { mark[i][next.s]=next.t; q.push(next); } } }}int main(){ int a,b,c,i,j; while(scanf("%d%d",&n,&m)!=-1) { for(i=0;i<=n;i++) for(j=1;j<=n;j++) g[i][j]=(i==j?

0:inf); for(i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); g[a][b]=g[b][a]=min(g[a][b],c); } ans=inf; inti(); bfs(); if(ans==inf) ans=-1; printf("%d\n",ans); } return 0;}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117246.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号