hdoj 3001 Travelling 【3进制+旅行商】

た入场券 2022-08-12 14:00 162阅读 0赞

题目：[hdoj 3001 Travelling][]

题意：标准的旅行商加一句话，每个点最多走两次。

分析：状态转移方程一模一样，只是要三进制，因为每个点有三种状态 0 ，1 2

定义状态：dp【st】【i】 ：在状态为 st 时 当前在 i 点的最小花费

转移方程：dp【now】【j】 = min（dp【now】【j】，dp【st】【i】+mp【i】【j】）；now是st可以一次转移得到的状态

注意初始化。

分析：

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <vector>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 12;
    int mp[N][N];
    int n,m;
    int bit[N],v[N];
    int dp[60000][N];
    void isit()
    {
        bit[0]=1;
        for(int i=1;i<N;i++)
            bit[i]=bit[i-1]*3;
    }
    void solve(int st)
    {
        memset(v,0,sizeof(v));
        int tmp=0;
        while(st)
        {
            v[tmp++]=(st%3);
            st/=3;
        }
    }
    int count()
    {
        int ans=0;
        for(int i=0;i<n;i++)
            ans+=(v[i]*bit[i]);
        return ans;
    }
    int main()
    {
        isit();
        while(~scanf("%d%d",&n,&m))
        {
            memset(mp,inf,sizeof(mp));
            for(int i=0;i<m;i++)
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                x--,y--;
                mp[x][y]=mp[y][x]=min(z,mp[x][y]);
            }
            memset(dp,inf,sizeof(dp));
            for(int i=0;i<n;i++)
            {
                dp[bit[i]][i]=0;
            }
            int ans=inf;
            for(int st=0;st<bit[n];st++)
            {
                int ok=1;
                solve(st);
                for(int i=0;i<n;i++)
                {
                    if(v[i]==0)
                        ok=0;
                    if(dp[st][i]==inf)
                        continue;
                    for(int j=0;j<n;j++)
                    {
                        if(v[j]==2 || i==j)
                            continue;
                        if(mp[i][j]==inf)
                            continue;
                        v[j]++;
                        int no=count();
                        dp[no][j]=min(dp[no][j],dp[st][i]+mp[i][j]);
                        v[j]--;
                    }
                }
                if(ok)
                    for(int i=0;i<n;i++)
                        ans=min(ans,dp[st][i]);
            }
            if(ans==inf)
                ans=-1;
            printf("%d\n",ans);
        }
        return 0;
    }

[hdoj 3001 Travelling]: http://acm.hdu.edu.cn/showproblem.php?pid=3001