hdu 3001（三进制状压）

题目

解法

看到这道题，我们就会想到旅行商问题。但是这里每一个点可以经过最多两次，所以我们用三进制表示就好了。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <cctype>

#include <vector>

#define INF 2139062143

#define MAX 0x7ffffffffffffff

#define del(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

template<typename T>

inline void read(T&x)

{

    x=;T k=;char c=getchar();

    while(!isdigit(c)){if(c=='-')k=-;c=getchar();}

    while(isdigit(c)){x=x*+c-'';c=getchar();}x*=k;

}

const int maxn=;

int dis[maxn][maxn];

int dp[][maxn];

int poww[];

void _init() {

    poww[]=;

    for(int i=;i<=;i++) poww[i]=poww[i-]*;

    return;

}

int query(int s,int k) {

    return s/poww[k]%;

}

int add(int x,int k) {

    return x+poww[k];

}

int n,m;

bool check(int x) {

    for(int i=;i<n;i++) if(!query(x,i)) return ;

    return ;

}

int main()

{

    _init();

    while(~scanf("%d %d",&n,&m)) {

        del(dis,);del(dp,);

        for(int i=,u,v,w;i<=m;i++) {

            read(u),read(v),read(w);--u,--v;

            dis[u][v]=min(dis[u][v],w);

            dis[v][u]=min(dis[v][u],w);

        }

        for(int i=;i<n;i++) dp[add(,i)][i]=;

        int ans=INF;

        for(int s=;s<poww[n];s++) {

            for(int i=;i<n;i++) {

                if(!query(s,i)) continue;

                for(int j=;j<n;j++) {

                    if(j==i||query(s,j)==||dis[i][j]==INF) continue;

                    dp[add(s,j)][j]=min(dp[s][i]+dis[i][j],dp[add(s,j)][j]);

                }

                if(check(s)) ans=min(ans,dp[s][i]);

            }

        }

        if(ans==INF) printf("-1\n");

        else printf("%d\n",ans);

    }

    return ;

}