kmjp's blog

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

AtCoder ABC #236 : G - Good Vertices

読み替えに気付くかがカギ。
https://atcoder.jp/contests/abc236/tasks/abc236_g

問題

N頂点T有向辺のグラフが与えられる。
T個の辺は順番がつけられている。

f(i)を、T個の辺のうち先頭f(i)個の辺だけ利用できるとき、1番の頂点からi番の頂点に、ちょうどL回辺に沿った遷移をすることで到達できるような最小の値とする。
各頂点iについてf(i)を答えよ。

解法

j番目の辺の重みをjとすると、f(i)は重みf(i)以下の辺だけでi番の頂点に到達できるような最小の重み、となる。

E(u,v,n) := 辺に沿ってn回移動したとき、u→vに遷移できるような最小の重み(どうやっても遷移不可な場合はinf)
とすると、EをダブリングすることでE(1,i,L)を求めればこれがf(i)となる。

int N,T,L;
const int MAT=100;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);v[0][0]=v[1][1]=1;};}; //

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]=1<<20;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		chmin(r.v[x][y],max(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]=(x==y)?0:(1<<20);
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}




void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T>>L;
	Mat A;
	FOR(x,N) FOR(y,N) A.v[x][y]=1<<20;
	FOR(i,T) {
		cin>>x>>y;
		A.v[y-1][x-1]=i+1;
	}
	
	A=powmat(L,A,N);

	FOR(i,N) {
		x=A.v[i][0];
		if(x==1<<20) x=-1;
		cout<<x<<" ";
	}
	cout<<endl;
	
	
}

まとめ

この言い換え賢いな。