Travelling（三进制状态压缩） · znzryb
## 思路讲解
状压dp最好都用0-based
这道题就是**三进制状态压缩的板子题**
之所以使用三进制，是因为2进制只能表示这个东西选没选，如这个经典的吃奶酪。
三进制可以表示这个城市来过一次or两次
[](https://www.notion.so/14d4539447bd8028baf6efcfe01fa70a)
## AC代码
```cpp
#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。