OUPC2012 問題L Sort (AOJ2361)

AOJ 数学問題

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2361）

制約条件

n≦8
0≦c[i][j]≦10^5
cは対称行列

方針

0 1 2 3 4 5 6 7の配列を入れ替えるDijkstraをすればいい。
状態数が8!と少ないので間に合う。


配列はビット表現で一つの整数に圧縮しないとTLEする。

ソースコード

int main(){
	int n,p[8][8],a=0;
	cin>>n;
	rep(i,n)rep(j,n)cin>>p[i][j];
	rep(i,n)a|=i<<3*i;
	set<int> v;
	priority_queue<pi> q;
	q.push(mp(0,a));
	int ans=0;
	while(!q.empty()){
		a=q.top().second;
		int c=q.top().first; q.pop();
		if(v.count(a))continue;
		ans=max(ans,-c);
		v.insert(a);
		rep(i,n)rep(j,i){
			a+=((a>>3*i&7)<<3*j)-((a>>3*j&7)<<3*j)+((a>>3*j&7)<<3*i)-((a>>3*i&7)<<3*i);
			if(!v.count(a))q.push(mp(c-p[i][j],a));
			a+=((a>>3*i&7)<<3*j)-((a>>3*j&7)<<3*j)+((a>>3*j&7)<<3*i)-((a>>3*i&7)<<3*i);
		}
	}
	cout<<ans<<endl;
	return 0;
}