ABC180 E bitDPの遷移がわからない

Question

AtCodedrのABC180E問題のbitDP

ABC180のEが、初めてbitDPでした。
解説見て自分で実装してみましたが、WAになってしまいます。

dpのところのfor文の順番を変えると通りました。
しかし、なぜ順番を変えて通ったのかよくわかりません。

該当のコード

以下がWAになったコードです。

#include<bits/stdc++.h>
using namespace std;

#define INF 1001001001 

int main(){

	int n;
	cin >> n;
	vector<int> x(n),y(n),z(n);
	for(int i=0;i<n;i++) cin >> x[i] >> y[i] >> z[i];
	int max_bit=(1<<n);
	
	//距離計算
	vector<vector<int>> dist(n,vector<int>(n));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j)continue;
			int cost=abs(x[j]-x[i]);
			cost+=abs(y[j]-y[i]);
			cost+=max(0,z[j]-z[i]);
			dist[i][j]=cost;		
		}
	}

	//dp[i][S]=iにいて(S)まわったときの、minコスト
	vector<vector<int>> dp(n,vector<int>(max_bit,INF));
	for(int i=1;i<n;i++){
		dp[i][1<<i]=dist[0][i];
	}
	
	for(int i=0;i<n;i++){
		for(int s=0;s<max_bit;s++){
			for(int j=0;j<n;j++){
			  if(~s>>i&1)break;//sにiが含まれていなかったらcontinue;
				if(s>>j&1)continue;//sにiが含まれてたらcontinue;
				dp[j][s|(1<<j)]=min(dp[i][s]+dist[i][j],dp[j][s|(1<<j)]);
			}
		}
	}


	cout << dp[0][max_bit-1] << endl;
}

dpの遷移のところを以下のように変更すると通りました。

	for(int s=0;s<max_bit;s++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(~s>>i&1)continue;//sにiが含まれていなかったらcontinue;
				if(s>>j&1)continue;//sにiが含まれてたらcontinue;
				dp[j][s|(1<<j)]=min(dp[i][s]+dist[i][j],dp[j][s|(1<<j)]);
			}
		}
	}

試したこと

以下を追加して遷移を見てみました。
cout << "s:" << bitset<4>(s) << ",i:" << i << ",j:" << j << endl;
なんとなく、通った点の集合Sを元にfor文を回さないといけないような気はしますが、何故なのかは明確にわかりません。

Answer 1

dp[j][s|(1<<j)]=min(dp[i][s]+dist[i][j],dp[j][s|(1<<j)]);

このコードでdp[i][s]を経由してdp[j][s|(1<<j)]に至る最短経路を更新しようと思ったら、
この時点でdp[i][s]は最短距離を示してないといけません。ところが最初のほうのコードだと、この時点でiまでの地点を経由する距離しか考慮されていないのでこれが最短距離である保証はありません。なので正しい答えが出ません。

Comments

[kyokio]

回答ありがとうございます。
sとiとjを出力してみて、yudedako67さんの言っていることがわかりました。

sはfor文を回していくうちに、通った場所の個数(立っているbitの数)が増えているから、
dp[i][s|(1<<j)]の最短経路を更新する時には、通った場所の個数が少ないdp[i][s]の最短経路は求まっているということなんですね。

理解できました。
ありがとうございます。