SRM579 div1 450

問題

店がN個あり、0からインデクスがふってある。

0〜M-1の店に興味があり、そこで商品を買いたい(1度だけ購入することができる)。
興味のあるお店については、開店時間、閉店時間、買い物にかかる時間が与えられる。
また、いくつかの店間には道があり、その移動時間も与えられる。

最初(時間0)では、店N-1にいる。
そこからスタートし、できるだけ興味のあるお店の商品を買いたい。
最大で買える商品数を答える。

考え方

問題を「各店間の距離を求める」と「興味のある店をできるだけ回る」の2つに分ける。
前者は全点間最短距離、後者はbitDPで求められる。

各点間の距離は、ワーシャルフロイドで全点間最短距離を求められるので、求める。

興味のある店をできるだけ回るは、同じ店で2回以上購入することがないので、
単純に
　dp[今いる店][今まで訪れた店集合]=かかった時間の最小時間
のbitDPになる。

まず、N-1から興味がある各店へ行ける場合、そこでまず購入できるので、
　そこへの移動時間＋開店までの待ち時間＋購入時間
をdp[i][1<