思考の墓場

はじめに ~この記事の経緯~ AtCoderで久々にBellman-Ford法を要求する問題が出題されました。Bellman-Ford法は蟻本でも紹介されている有名な単一始点最短経路アルゴリズムであり、負閉路の検出を行うこともできます。ところが今回扱う問題では、この負閉路検出の部分に工夫が必要です。過去にほぼ同様の問題が出題されたこ…