olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

タクシー(14予選5)

N個の町、K本の道がある。各町にはタクシー会社が存在し、それぞれ決められた数までの道を移動できる。また、料金も決まっている。

1~Nに移動するために必要なコストの最小値を求める問題。

基本的にはdijkstraでよいが、各頂点を訪れるごとに移動できる場所をまとめる。(あらかじめまとめておくとMLEになった)

計算量はO(N^2logN)

難易度は8程度に感じられた

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2322477#1