TopCoder SRM 795 : Div1 Easy Div2 Hard AtLeastKDays

最近Mediumのポカミスが多いなぁ。
https://community.topcoder.com/stat?c=problem_statement&pm=16704&rd=18429

問題

N頂点の完全グラフがあり、辺にはコストが設定されている。
f(u,v)を、頂点uからvまでD回以上隣接辺を遷移して到達した際の総コストの総和の最小値とする。
全頂点対(u,v)に対しf(u,v)の総和を求めよ。

解法

g(u,v,p) := 頂点uからvまで、ちょうどp回の遷移で到達したときのコストの最小値
とすると、行列累乗の要領でg(u,v,D)を求めることができる。
ただし、2頂点でuとvが同じケースなど、D回の遷移で元の場所に戻れない場合もある。

そこで以下をWarshall-Floydで求めておこう。
h(u,v) := 遷移回数を問わず頂点uからvまで遷移する最小コスト
解はmin(g(u,w,D)+h(w,v))となる。

ll D[50][50];

const int MAT=50;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};

Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=1LL<<60;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y]=min(r.v[x][y],a.v[x][z]+b.v[z][y]);
	}
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=1LL<<60;
	FOR(i,n) r.v[i][i]=0;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

class AtLeastKDays {
	public:
	long long sumOfMinCosts(vector <string> costs, int minDays) {
		int N=costs.size();
		int y,x,z;
		Mat A;
		FOR(y,N) FOR(x,N) {
			if(x==y) D[y][x]=A.v[y][x]=1LL<<60;
			else D[y][x]=A.v[y][x]=costs[y][x]-'0';
		}
		FOR(z,N) FOR(y,N) FOR(x,N) D[y][x]=min(D[y][x],D[y][z]+D[z][x]);
		A=powmat(minDays,A,N);
		
		ll ret=0;
		FOR(y,N) FOR(x,N) {
			ll mi=A.v[y][x];
			FOR(z,N) mi=min(mi,A.v[y][z]+D[z][x]);
			ret+=mi;
		}
		return ret;
	}
}

まとめ

Easyにしてはちょっと面倒なので、300ptは妥当か。