問題

https://community.topcoder.com/stat?c=problem_statement&pm=14091&rd=16625 

<p>
  n個の街がある。二つの街を移動するには、dist[i][j]時間かかる.
</p>

<p>
  また、k magic pointが与えられる。 magic pointをつかうと移動時間を半分にすることができる.
</p>

<p>
  街0から1への最小の移動時間を求めよ.
</p>

方針

ダイクストラ法をつかうのだと思った. 

<ul class="org-ul">
  <li>
    <a href="https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95">ダイクストラ法 - Wikipedia</a>
  </li>
</ul>

<p>
  以下のリンクを参考に実装してみた.
</p>

<ul class="org-ul">
  <li>
    <a href="https://www.deqnotes.net/acmicpc/dijkstra/">ダイクストラ法（最短経路問題）</a>
  </li>
  <li>
    <a href="https://www.geocities.jp/m_hiroi/light/pyalgo67.html">Algorithms with Python / ヒープ</a>
  </li>
  <li>
    <a href="https://lethe2211.hatenablog.com/entry/2014/12/30/011030">Pythonでダイクストラアルゴリズムを実装した - フツーって言うなぁ！</a>
  </li>
</ul>

<p>
  ポイントは、magic pointをk回つかうことで、最小の移動時間が変動すること. 0から1へk回 magic pointをつかった結果を記憶しておいて、 最後に、その結果のなかでの最小値を求める.
</p>

<p>
  で、いいのかな?? よくわからず、もう5時間くらい悩んでいるのだけれども。。。
</p>

回答