競プロの記録 (2016_09_30)
今日は星2を1問のみ。
数は少なすぎるけど、やっと星2を解いた。
途中で止まる地点が、2点以上というのが肝。
その2点間に何を経由するかは関係なしで、単純に2点間の距離を求める。
こういう時はワーシャルフロイド法を使うのが一般的なようだ。
今回初めて実装した。ダイクストラよりはずっと簡単な実装だ。
あとは、2点間の距離と、それぞれの点からの0、N-1への距離の和が最も小さくなるように選ぶだけ。
このように終わってから文章で書くと、非常に単純で簡単な問題に思えてくる。
この感覚を忘れないようにしたい。
B予選まであと10日。