n-knuu's logs

憧れ駆動。だいたい競プロ

CODE THANKS FESTIVAL 2015 G - カメレオン

Dijkstra atcoder

問題

G: カメレオン - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder

解法

dist[v][c] = (頂点vでの色がcのときの頂点0から頂点vまでの最短距離)としてDijkstra法を適用する。
ただし、蟻本のDijkstraのコードに加えて以下を加えないとTLE/MLEする

  1. cが0以上10^9以下なので、dist[]を辞書型(C++ならmap)で持っておく必要がある
  2. 頂点Nまでの最短距離さえ求められればよいので、Nに最初に到達したらその時点で探索を終了する

コード


感想