kmjp's blog

競技プログラミング参加記です

Codeforces #319 Div1 D. Flights for Regular Customers

うーむ、落ち着いて考えるとそう難しくない。
http://codeforces.com/contest/576/problem/D

問題

1~N番のN頂点M有向辺のグラフがある。

ただし各辺はパラメータD[i]があり、過去にD[i]回以上辺を遷移していないと利用できない。
1番の頂点からN番の頂点に至る辺の最小遷移回数を求めよ。

解法

ある時刻において居る可能性の頂点群から、その時点で利用可能な辺を使って頂点群Nに到達可能かどうかは適当に辺を辿ればO(N+M)で判定できる。
また、現在遷移可能な辺だけで頂点Nに到達できるなら、最大M回遷移を繰り返すまでの間にたどり着けるはずなのでO(NM)の遷移処理で回数を求められる。
N,Mは上限150と小さいので、これらの処理はさほど重くない。

あとは頂点Nに到達可能になるまでの処理である。
有向辺を行列表現すると、行列の積で複数回の遷移を表現できるし、行列の累乗を使ってO(log(遷移回数)*N^3)で処理できる。
つまり、頂点Nに到達可能になるまで順次辺を追加していき、その都度移動可能な範囲を行列の積・累乗で処理していく。

最悪で辺の追加回数分だけ行列の累乗が生じるのでO(log(maxD)*N^3*M)かかり、このままだとTLEする。
ただ、この行列は遷移可否の01だけで表現できるので64bit整数に64個分の遷移を畳み込めるのでそれで間に合う。

int N,M;
int A[200],B[200],D[200];
map<int,vector<int>> MM;
set<int> S;

struct mat { ll v[150][3]={};};
struct vec { ll v[3]={};};

mat mult(mat a,mat b,int n) {
	mat c,d; int x,y,z;
	FOR(x,n) FOR(y,n) if(b.v[y][x/64] & (1LL<<(x%64))) c.v[x][y/64] |= 1LL<<(y%64); // rot
	FOR(x,n) FOR(y,n) {
		ll v=0;
		FOR(z,(n+63)/64) v |= a.v[x][z] & c.v[y][z];
		v=(v!=0);
		d.v[x][y/64] |= v<<(y%64);
	}
	return d;
}
mat init(int n) {
	mat r; int x;
	FOR(x,n) r.v[x][x/64] |= 1LL<<(x%64);
	return r;
}
mat powm(mat a,int p,int n) {
	mat r=init(n);
	while(p) {
		if(p%2) r=mult(r,a,n);
		a=mult(a,a,n);
		p/=2;
	}
	return r;
}
vec mult(mat a,vec b,int n) {
	vec c;
	int x,y;
	FOR(x,n) if(b.v[x/64] & (1LL<<(x%64))) FOR(y,(n+63)/64) c.v[y] |= a.v[x][y];
	return c;
}

bool reachable(mat a,vec b) {
	int x,y;
	
	FOR(x,150) {
		vec c=mult(a,b,N);
		b.v[0] |= c.v[0];
		b.v[1] |= c.v[1];
		b.v[2] |= c.v[2];
	}
	int n=N-1;
	return (b.v[n/64] & (1LL<<(n%64)))!=0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>D[i];
		A[i]--;B[i]--;
		MM[D[i]].push_back(i);
		S.insert(D[i]);
	}
	
	int cur=0;
	vec v;
	mat m;
	v.v[0]=1;
	FORR(r,MM) {
		
		v = mult(powm(m,r.first-cur,N),v,N);
		cur=r.first;
		FORR(r2,r.second) m.v[A[r2]][B[r2]/64] |= 1LL<<(B[r2]%64);
		
		if(reachable(m,v)) break;
	}
	
	if(!reachable(m,v)) return _P("Impossible\n");
	
	int n=N-1;
	while((v.v[n/64] & (1LL<<(n%64)))==0) {
		v = mult(m,v,N);
		cur++;
		if(S.count(cur)) FORR(r2,MM[cur]) m.v[A[r2]][B[r2]/64] |= 1LL<<(B[r2]%64);
	}
	cout<<cur<<endl;
	
}

まとめ

こう見るとそれほど複雑なことはやってないんだよな。