enakai00 https://blog.hatena.ne.jp/enakai00/ めもめも https://enakai00.hatenablog.com/ 何の話かと言うと enakai00.hatenablog.com前回の続きです。 ノードを消していく発想（もしくは、トポロジカルオーダーによる処理） 前回のアルゴリズムの計算量を考えてみましょう。 for x in range(1, N+1): for y in range(1, N+1): if dp[y][x] == 0: continue for z in range(1, N+1): if dp[x][z] == 0: continue この3重ループからわかる様に最悪ケースで です。大部分の dp[x][y]、dp[y][z] が 0 であれば、リンク情報を別のデータ構造に持たせた、… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fenakai00.hatenablog.com%2Fentry%2F2021%2F07%2F16%2F215232" title="G - Longest Path の解説（その2） - めもめも" 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 2021-07-16 21:52:32 rich https://enakai00.hatenablog.com/entry/2021/07/16/215232 1.0 100%