yukicoder No.848 なかよし旅行

問題

N個の町がM本の道でつながっており、道の移動にかかる時間が与えられる。
今、2人が町1にいるが、T分以内に町Pと町Qを回って町1に戻ってきていなければならない。
町Pと町Qは2人のうちどちらか1人でも回ればよい。
ただし、道の途中で引き返すような行動はとれない。

2人はできるだけ一緒に行動したいが、最大で何分一緒に行動できるか？
不可能な場合は-1を出力せよ。

制約

• 3 <= N <= 2000
• 2 <= M <= 10^5
• 2 <= P <= Q <= N
• 1 <= T <= 10^9
• 1 <= ある道の移動時間 <= 10^9
• すべての町は町1から歩いていくことができる

解法

まず、全部一緒に回れるかどうかを考える。
1->P->Q->1と一緒に回る時間がT分以下だった場合、適当に待ち時間を入れることで答えをTにできる。

上記でない場合は、何分かの間、別行動が発生する。
別行動をしている時間をtとすると、答えはT-tになる。

ある頂点xまで行って、それぞれP,Qに別々に移動して、xに戻ってくることを考えると、x->P->xかx->Q->xの長い方の時間だけかかる。
しかし、例えば、x->Pが1、x->Qが10のような場合、x->Q->xの20だけかかるが、P->yが10、Q->yが1のようなyが存在する場合、x->P->yとx->Q->yが11ほどとなり、y->1が1->xと同じでもそのルートを通った方が短くなる。

したがって、x,yのペアをすべて確認し、t={x->P->yかx->Q->yの長い方}として、T-tで一番長いものを求めればよい。

反省

さっと思いつくgreedyの「同じ場所xに戻る」のが嘘解法だというのに気付くのが難しい、、、