Codeforces #580 Div1 B. Shortest Cycle

だいぶ手間取ってしまった。
https://codeforces.com/contest/1205/problem/B

問題

N頂点のグラフを考える。
N要素の整数列A[i]が与えられる。
A[i]とA[j]のbitwise-andが正であれば、頂点i,j間に辺があるとする。

最短の閉路長を求めよ。

解法

同じビットが立っている要素が3つ以上あれば、長さ3の閉路ができる。
そうでない場合、同じビットは2個以上たたないので、A[i]が0でない要素は120個程度しか現れない。
こうなると総当たりでDFSして閉路を求められる。

int N;
ll A[101010];
int num[64];

vector<int> V[5000];
int mi=10101;

int D[150][150][150];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>A[i];
		if(A[i]==0) {
			i--;
			N--;
			continue;
		}
		FOR(x,62) if(A[i]&(1LL<<x)) {
			num[x]++;
			if(num[x]>=3) return _P("3\n");
		}
	}
	
	FOR(x,N) FOR(y,N) {
		if(A[x]&A[y]) V[x].push_back(y);
	}
	
	FOR(i,N) FOR(j,N) FOR(k,N) D[i][j][k]=10101;
	queue<int> Q;
	FOR(i,N) {
		D[i][i][i]=0;
		Q.push(i*1000000+i*1000+i);
	}
	
	while(Q.size()) {
		int s=Q.front()/1000000;
		int pre=Q.front()/1000%1000;
		int cur=Q.front()%1000;
		Q.pop();
		FORR(e,V[cur]) {
			if(e==pre || e==cur) continue;
			if(e==s) return _P("%d\n",D[s][pre][cur]+1);
			if(D[s][cur][e]>D[s][pre][cur]+1) {
				D[s][cur][e]=D[s][pre][cur]+1;
				Q.push(s*1000000+cur*1000+e);
			}
		}
	}
	
	cout<<-1<<endl;
	
}

まとめ

なぜこんなかかってしまったのか。