Codeforces #718 Div1+2 : D. Explorer Space

なんだこれ。
https://codeforces.com/contest/1517/problem/D

問題

グリッドグラフが与えられ、各辺の重さが与えられる。
各点から初めて、辺をちょうどK回遷移して元の点に戻るとき、経由した辺の重さの合計の最小値をそれぞれ求めよ。

解法

Kが奇数のときは解なし。
Kが偶数の時は、各点から初めてK/2回移動した場合の重みの総和の最小値を求め、2倍すればよい。

int H,W,K;
vector<pair<int,int>> E[505*505];
int dp[505*505][11];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) {
		FOR(x,W-1) {
			cin>>k;
			E[y*W+x].push_back({y*W+x+1,k});
			E[y*W+x+1].push_back({y*W+x,k});
		}
	}
	FOR(y,H-1) {
		FOR(x,W) {
			cin>>k;
			E[y*W+x].push_back({y*W+x+W,k});
			E[y*W+x+W].push_back({y*W+x,k});
		}
	}
	
	if(K%2==1) {
		FOR(y,H) {
			FOR(x,W) cout<<"-1 ";
			cout<<endl;
		}
		return;
	}
	K/=2;
	FOR(y,H) {
		FOR(x,W) {
			FOR(i,11) dp[y*W+x][i]=1<<30;
		}
	}
	FOR(y,H) {
		FOR(x,W) {
			int y2,x2;
			dp[y*W+x][0]=0;
			int ret=1<<30;
			for(i=0;i<=K;i++) {
				for(y2=max(0,y-i);y2<=min(H-1,y+i);y2++) {
					int lef=i-abs(y2-y);
					for(x2=max(0,x-lef);x2<=min(W-1,x+lef);x2++) {
						//cout<<y<<x<<" "<<y2<<x2<<i<<" "<<dp[y2*W+x2][i]<<endl;
						if(i==K) {
							ret=min(ret,dp[y2*W+x2][K]);
						}
						else {
							FORR2(e,c,E[y2*W+x2]) dp[e][i+1]=min(dp[e][i+1],dp[y2*W+x2][i]+c);
						}
						dp[y2*W+x2][i]=1<<30;
					}
				}
			}
			cout<<ret*2<<" ";
		}
		cout<<endl;
	}
	
}

まとめ

特に工夫がいる気もしないし、この問題の肝は何だったんだろう。