Codeforces #623 Div1 D. Tourism

B,CよりもAC数が多い。
https://codeforces.com/contest/1314/problem/D

問題

N頂点の有向完全グラフがあり、各辺のコストが与えられる。
ここで、頂点1から始まり頂点1に戻る長さK(Kは偶数)の閉路を考える。
その際、奇数長の閉路を通ることがあってはならない。
条件を満たす閉路の最小コストを求めよ。

解法

頂点対U,Vに対し、U→X→Vと間を1点経由する経路を事前に列挙し、長さを降順に求めておく。
これを踏まえ、2頂点毎に通るパスを総当たりしよう。
例えばK=8なら1→*→A→*→B→*→C→*→1と遷移する。
この時、*の部分は1,A,B,C以外であればいいので、事前に求めた2頂点の移動方法のうち上位5個まで見れば奇閉路の生じない経路を選べる。

vector<pair<ll,int>> M[80][80];
int N,K;
ll mat[81][81];
int A[81];
ll ret=1LL<<60;

void dfs(vector<int>& V) {
	if(V.size()==K/2) {
		V.push_back(0);
		ll sum=0;
		int i;
		FOR(i,K/2) {
			FORR(a,M[V[i]][V[i+1]]) {
				if(A[a.second]==0) {
					sum+=a.first;
					break;
				}
			}
		}
		ret=min(ret,sum);
		V.pop_back();
		return;
	}
	
	int i;
	for(i=0;i<N;i++) {
		V.push_back(i);
		A[i]++;
		dfs(V);
		A[i]--;
		V.pop_back();
	}
}

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>K;
	FOR(y,N) FOR(x,N) cin>>mat[y][x];
	
	FOR(x,N) FOR(y,N) {
		FOR(z,N) if(z!=x && z!=y) {
			M[x][y].push_back(make_pair(mat[x][z]+mat[z][y],z));
		}
		FOR(i,10) M[x][y].push_back({1LL<<50,80});
		sort(ALL(M[x][y]));
	}
	vector<int> V;
	V.push_back(0);
	A[0]++;
	dfs(V);
	
	cout<<ret<<endl;
}

まとめ

Cの方が難しいよね…。