うーむ、落ち着いて考えるとそう難しくない。
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; }
まとめ
こう見るとそれほど複雑なことはやってないんだよな。