1511

A点からB点への移動コストが与えられるので、0番目の地点にN人の人がいて、それぞれ、1,2,...,N番目の地点に行って帰ってくるとき、最小のコストを求めよ、という問題。

行くだけのコストならダイクストラをやるだけ。帰ってくるコストについては、開始点がバラバラだと面倒なので、辺の向きを逆にして開始点からダイクストラをする。これで帰ってくるコストになる。かなり重たいけれど、時間は長めなので大丈夫。