Znzryb's Blog
0%

Travelling（三进制状态压缩）

Posted on Edited on

思路讲解

状压dp最好都用0-based

这道题就是三进制状态压缩的板子题

之所以使用三进制，是因为2进制只能表示这个东西选没选，如这个经典的吃奶酪。

三进制可以表示这个城市来过一次or两次

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
// https://vjudge.net/problem/HDU-3001
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,m;
ll road[15][15];
ll dp[60000][12];	// 状态i以j收尾的最少费用
ll three[12];
ll digit[60000][12];	// 状态i的第j位数字是什么
const ll INF=99999999;

void init(){
	three[0]=1;
	for(int i=1;i<=10;++i)
		three[i]=three[i-1]*3;
	for(int i=0;i<three[10];++i){
		int temp=i;
		for(int j=0;j<10;++j){
			digit[i][j]=temp%3;
			temp/=3;
		}
	}
}

void init2(){
	memset(road, 0x3f, sizeof(road));
	memset(dp, 0x3f, sizeof(dp));
	for(int i=1;i<=n;++i)	// 自己到自己的距离为0
		road[i][i]=0;
	for(int i=0; i<n; i++)
		dp[three[i]][i]=0;	///dp的初始化，将起点都找出来
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	init();
	while(cin>>n>>m){
		init2();
		for(int i=1;i<=m;++i){
			ll a,b,c;
			cin>>a>>b>>c;
			road[a][b]=min(c,road[a][b]);
			road[b][a]=min(c,road[b][a]);
		}
		ll ans=INF;
		for(int i=1;i<three[n];++i){
			bool flag=true;
			for(int j=0;j<n;++j){	// 枚举i状态以j结尾
				if(!digit[i][j]){
					continue;
				}
				for(int k=0;k<n;++k){	
					// 枚举i状态是从k结尾状态转移到j结尾状态的
					if(!digit[i][k]){
						flag=false;
						continue;
					}
					dp[i][j]=min(dp[i-three[j]][k]+road[k+1][j+1],dp[i][j]);
				}
				if(flag)
					ans=min(ans,dp[i][j]);
			}
		}
		
//		for(int i=0;i<n;++i)
//			ans=min(ans,dp[three[n]-1][i]);
		cout<<(ans==INF ? -1:ans)<<endl;
	}
	return 0;
}
/*
AC https://vjudge.net/solution/57067144
2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10
c

*/

心路历程（WA，TLE，MLE……）

前面调了半天，以为是我的写法有问题，但其实是因为

dp[i][j]=min(dp[i-three[j]][k]+road[k+1][j+1],dp[i][j]);

写成了road[k-1][j-1]

路程匹配错误导致了这个问题

C语言也是的，这个index都超范围了也不给个提示，6。