首页 > ACM题库 > HDU-杭电 > HDU 3001-Travelling-动态规划-[解题报告]HOJ
2014
02-26

HDU 3001-Travelling-动态规划-[解题报告]HOJ

Travelling

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

100
90
7 

题目:hdu 3001 Travelling 

状态方程:dp[state][i] = min(dp[state][i] , dp[state-j][j]+cnt[j][i]) 类似 floyd    // dp[state][i] 表示状态state下,终点为i,遍历所有城市的最短路径

但是由于每个城市最多只能经过两次,所以我们用3进制来表示该城市被经过的次数。

注意:注意重边的存在。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[60000][11];
int cnt[11][11];
int three[12];
int m,n;
int f[60000][11];
void init()
{
    three[1]=1;
    for(int i=2;i<=11;i++)
        three[i]=three[i-1]*3;
    for(int i=0;i<three[11];i++)
    {
        int tmp=i;
        for(int j=1;j<=10;j++)
        {
            f[i][j]=tmp%3;
            tmp/=3;
        }
    }
}
int main()
{
    init();
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,0x7f,sizeof(dp));
        memset(cnt,0x7f,sizeof(cnt));
        int ans=dp[0][0];
        int inf=ans;
        int x,y,d;
        while(m--)
        {
            scanf("%d%d%d",&x,&y,&d);
            cnt[x][y]=cnt[y][x]=min(cnt[x][y],d);
        }
        for(int i=1;i<=n;i++)
            dp[three[i]][i]=0;
        for(int state=1;state<three[n+1];state++)
        {
            bool ok=1;
            for(int i=1;i<=n;i++)
            {
                if(f[state][i]==0)
                    ok=0;
                if(dp[state][i]==inf)
                    continue;
                for(int j=1;j<=n;j++)
                {
                    if(i==j)
                        continue;
                    if(f[state][j]==2)
                        continue;
                    if(cnt[i][j]==inf)
                        continue;
                    dp[state+three[j]][j]=min(dp[state+three[j]][j],dp[state][i]+cnt[i][j]);
                }
            }
            if(ok)
            {
                for(int i=1;i<=n;i++)
                {
                    ans=min(ans,dp[state][i]);
                }
            }
        }
        if(ans==inf)
            ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}

解题参考:http://blog.csdn.net/shiyuankongbu/article/details/9819059


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  4. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。