moistx https://blog.hatena.ne.jp/moistx/ Logfiles https://logfiles.hatenablog.com/ AOJ 解法 BFS (or Warshall-Floyd) BFSではノードの接続を隣接行列でなくて連結リストにして解いたけどその必要はあったのだろうか。 因みにnは100以下なので、コストを1に定めて Warshall-Floyd しても解ける。この方が実装が短いし、一度最短路を求めればクエリに対しての処理が楽になるので良い。反省点 問題文を読むときは１度で意味を取れるように読むこと。 問題文が読めれば実装は自明なはず。 ノードの入力を全て0-indexedに治す所とかは注意する。さすがにBFSは慣れてるだろうと、問題文読むのに一番時間が掛かったとしても20分くらいで書きたいところだった。けど実際… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Flogfiles.hatenablog.com%2Fentry%2F20140328%2F1395383822" title="AOJ0144 Packet Transportation - Logfiles" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-03-28 15:37:02 rich https://logfiles.hatenablog.com/entry/20140328/1395383822 1.0 100%