Locks and keys (UVa Live Archive Europe Southwestern 2010)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2963

問題

頂点数nの木がある。各辺にはドアがあり、鍵の必要な物がある。鍵が必要なドアはC個あり、各ドアには色がついていて同じ色の鍵を使えば開くことができる。また鍵はどこかの頂点に落ちていてる。鍵は同時に1つまでしか持ち歩くことは出来ないが、一度ドアを開けてしまえばその鍵はその場で捨ててしまって良く、そのドアはいつでも通ることができる。この条件でスタートからゴールの頂点まで行く経路を求めよ。ただし、経路の長さは4*(C+1)*nを超えては行けない。
1<=n<=1,500
1<=C

解法

頂点xから頂点yまで行く関数Move(x,y)を考える。鍵の付いてないドアは普通に通って良く、その頂点の列はtempとかに記憶しておく。錠がまだ付いてるドアに対応する鍵のある頂点をzとするとMove(x,z),Move(z,x)を呼び出し、tempの列と次の頂点x'を答えの列に入れ、x=x'とする。その様な操作を繰り返して、yまでたどり着いたら、まだ残ってるtempを答えの列に入れ終了する。途中で錠がまだ付いてる同じドアを2回以上訪れた場合はImpossibleになる。xからyに行く時にどの辺を選ぶべきかはO(n^2)で前処理しておけばO(1)で求めれる。