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)


相关推荐

  • bat蠕虫病毒_病毒驱动器

    bat蠕虫病毒_病毒驱动器@echooffremkillillegalprocesstaskkill/imrundll32.exe/ftaskkill/imwsctf.exe/ftaskkill/imexplorer.exe/ftaskkill/im2EB49F.exe/ftaskkill/imwinhcreg.exe/ftaskkill/imAE1283.EXE/ftask

  • HDU 2647 Reward 【拓扑排序反向建图+队列】

    HDU 2647 Reward 【拓扑排序反向建图+队列】

  • 微信h5支付,微信外浏览器支付实现

    微信h5支付,微信外浏览器支付实现2021-02-07修改看一下官方文档还是很必要的,知道必不可少的参数是什么:https://pay.weixin.qq.com/wiki/doc/api/H5.php?chapter=9_20&index=1下面按步骤跟着我做首先需要APPID,微信支付商户号mch_id,API密钥key,Appsecret(secret),说明在这里https://pay.weixin.qq.com/wiki/doc/api/H5.php?chapter=3_1 然后设置支付域名,设置路径:商户平

  • @Page指令中的AutoEventWireup

    @Page指令中的AutoEventWireup以前根本不注意AutoEventWireup这个小小的属性,但是后来由于它产生的许多麻烦使我不得不研究它,并最终领悟了它。如果你写了一个asp.net页面,里面包含了服务端脚本:voidPage_Load(objectsender,EventArgse){lblMessage.Text=”ThinkinginTechmango.com”;}

  • Java文件读写操作

    Java文件读写操作Java中I/O流对文件的读写有很多种方法,在这里我主要介绍三种方式,供大家参考。第一种方式:使用FileWriter和FileReader,对文件内容按字符读取,代码如下Stringdir="E:\\soft\\aaa\\a.txt";Filefile=newFile(dir);//如果文件不存在,创建文件if(!file.exists())file.c…

  • SpringBoot常见面试问题

    SpringBoot常见面试问题博客转载自:https://blog.csdn.net/ityouknow/article/details/96533522随着SpringBoot使用越来越广泛,SpringBoot已经成为Java程序员面试的知识点,很多同学对SpringBoot理解不是那么深刻,经常就会被几个连环跑给干趴下了!比如下面这一段的SpringBoot问答:问:你觉得S…

发表回复

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

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