【hdu3001】Travelling

题目描述

有一个人要去旅游，他想要逛遍所有的城市，但是同一个城市又不想逛超过2次。现在给出城市之间的来往路费，他可以选择任意一个点为起点。问逛遍所有城市的最低路费是多少？

输入

有多组数据。

每组数据第一行两个数 n，m，表示有n个点，m条边 ( n≤10 )。

接下来m行，每行三个整数x，y，z，表示 x 到 y 有一条值为 z 的边。

输出

最低路费。

样例输入

样例输出

100
90
7

题解

第一道非2进制的状压，自己实现了下二进制状压中的一些操作，但是应该不是最优的做法。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=10+5;
const int maxm=59049+50;
const int maxx=2139062143;

int n,m,dis[maxn][maxn],t,top,ad[maxm][maxn];
int S[maxn],T[maxn],b[maxn],dp[maxm][maxn];
bool isin[maxm][maxn],is2[maxm][maxn];

void to_3(int x){
    t=0;memset(S,0,sizeof(S));
    while(x>=3){
        S[++t]=x%3;x/=3;
    }
    S[++t]=x;
}

void To_3(int x){
    t=0;memset(T,0,sizeof(T));
    while(x>=3){
        T[++t]=x%3;x/=3;
    }
    T[++t]=x;
}

bool is_in(int x,int s){
    to_3(s);To_3(pow(3,x-1));
    for(int i=1;i<=10;i++)
    if(T[i]!=0&&S[i]!=0) return true;
    return false;
}

bool is_2(int x,int s){
    to_3(s);To_3(pow(3,x-1));
    for(int i=1;i<=10;i++)
    if(T[i]!=0) if(S[i]==2) return true;
    return false;
}

int add(int x,int s){
    to_3(s);To_3(pow(3,x-1));
    for(int i=1;i<=10;i++)
    if(T[i]==1) S[i]++;
    int ans=0;
    for(int i=1;i<=10;i++) ans+=S[i]*pow(3,i-1);
    return ans;
}

bool is_ok(int s){
    memset(S,0,sizeof(S));
    to_3(s);
    for(int i=1;i<=n;i++) if(S[i]==0) return false;
    return true;
}

template<typename T>void read(T& aa){
    char cc; ll ff;aa=0;cc=getchar();ff=1;
    while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
    if(cc=='-') ff=-1,cc=getchar();
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    aa*=ff;
}

void init(){
    for(int s=0;s<59049;s++){
        for(int i=1;i<=10;i++){
            isin[s][i]=is_in(i,s);
            is2[s][i]=is_2(i,s);
            ad[s][i]=add(i,s);
        }
    }
}

int main(){
    init();
    while(scanf("%d%d",&n,&m)!=EOF){
        int ans=maxx;
        memset(dis,-1,sizeof(dis));
        for(int i=1;i<=m;i++){
            int x,y,z;
            read(x),read(y),read(z);
            if(dis[x][y]==-1) dis[x][y]=dis[y][x]=z;
            else
            dis[x][y]=dis[y][x]=min(dis[x][y],z);
        }
        memset(dp,127,sizeof(dp));
        for(int i=1;i<=n;i++){
            int o=pow(3,i-1);
            dp[o][i]=0;
        } 
        top=pow(3,n);
        for(int s=0;s<top;s++){
            for(int i=1;i<=n;i++){
                if(!isin[s][i]) continue;
                for(int j=1;j<=n;j++){
                    if(j==i||is2[s][j]) continue;
                    int New=ad[s][j];
                    if(dis[i][j]==-1) continue;
                    dp[New][j]=min(dp[New][j],dp[s][i]+dis[i][j]);
                }
            }
        }
        for(int s=0;s<top;s++){
            if(is_ok(s)){
                for(int i=1;i<=n;i++) ans=min(ans,dp[s][i]);
            }
        }
        if(ans>=maxx) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}