HDU-3001 TSP + Ternary DP

Give an undirected graph. Each point can't be passed more than twice. Choose a starting point to ask the shortest path that passes all points at least once.

Solution: note that each point can not go through more than twice, which is different from the general TSP problem. But it doesn't make this problem very complicated. The original state is represented by binary compression, which is not enough. We have to represent 0 times, 1 time, 2 times. What do you think of? That's right. It can be represented in ternary. Other problems are similar to TSP problems. dp[S][x] represents the shortest path length through which s now completes the target at a distance of X points. dp as usual.

#include<bits/stdc++.h>
using namespace std;
const int M=10*10;
const int INF=0x3f3f3f3f; 
int n,m;

int cnt,head[M<<1],nxt[M<<1],to[M<<1],len[M<<1];
void add_edge(int x,int y,int z) {
    nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt;
}

int inc(int S,int x) {
    int p=1; for (;x>1;x--) p*=3;
    return S+p;
}
int get(int S,int x) {
    int t=1;
    while (t<=n) {
        if (t==x) return S%3;
        S/=3; t++;
    }
}
bool check(int S) {
    int t=1;
    while (t<=n) {
        if (S%3==0) return 0;
        S/=3; t++;
    }
    return 1;
}

int dp[200000][12];
int dfs(int S,int x) {
    if (check(S)) return 0;
    if (dp[S][x]!=-1) return dp[S][x];
    int ret=INF;
    for (int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if (get(S,y)<2) ret=min(ret,dfs(inc(S,y),y)+len[i]);
    }
    return dp[S][x]=ret;
}

int main()
{
    while (scanf("%d%d",&n,&m)==2) {
        cnt=1,memset(head,0,sizeof(head));
        for (int i=1;i<=m;i++) {
            int x,y,z; scanf("%d%d%d",&x,&y,&z);
            add_edge(x,y,z);
            add_edge(y,x,z);
        }
        memset(dp,-1,sizeof(dp));
        int ans=INF;
        for (int i=1;i<=n;i++) ans=min(ans,dfs(inc(0,i),i));
        if (ans==INF) puts("-1"); else printf("%d\n",ans);
    }
    return 0;
}

Tags: PHP

Posted on Fri, 01 Nov 2019 10:10:47 -0700 by BryonS