Paid Roads (PKU 3411)

http://poj.org/problem?id=3411

問題

N頂点、辺数mの有向グラフが与えられる。各辺は頂点cに行ったことがあるならばコストPi、そうでないならばRiで通れる。頂点1から頂点Nまで行く最小コストを求めよ。
N,m<=10

解法

たどり着いた街が同じ場合はn歩までしか歩けないようにしてメモ化再帰。もしくは状態数を2^nしたダイクストラ。