1476

ある都市からある都市への航空便の値段とその有無が与えられるので、開始都市から終了都市までK回の移動の最小コストを求めよ、という問題。

都市数が10でKが高々1000という状況なので、何も考えずにDPするだけ。

どこかに計算量的にまずいところがあってTLEするんじゃないかと思いつつ適当に投げてみたら通ってしまったという感じ。そもそも定数倍最適化するくらいしか思いつかないけれども。