tshimizu's diary

日々の記録

競プロの記録 (2016_09_30)

今日は星2を1問のみ。
数は少なすぎるけど、やっと星2を解いた。

No.17 2つの地点に泊まりたい - yukicoder

途中で止まる地点が、2点以上というのが肝。
その2点間に何を経由するかは関係なしで、単純に2点間の距離を求める。
こういう時はワーシャルフロイド法を使うのが一般的なようだ。
今回初めて実装した。ダイクストラよりはずっと簡単な実装だ。
あとは、2点間の距離と、それぞれの点からの0、N-1への距離の和が最も小さくなるように選ぶだけ。

このように終わってから文章で書くと、非常に単純で簡単な問題に思えてくる。
この感覚を忘れないようにしたい。

B予選まであと10日。