enakai00 https://blog.hatena.ne.jp/enakai00/ めもめも https://enakai00.hatenablog.com/ 何の話かと言うと atcoder.jpこの問題をネタにして、最短／最長経路に関する考え方を説明してみます。 経路問題の基本的な考え方 実際にはいくつかの考え方があって、問題にあわせてうまく選ばないといけないのですが、まずは、汎用性の高い考え方をおさえましょう。通常、経路問題では、隣り合ったノード間のリンクの情報だけが与えられます。つまり、他のノードを経由せずに、ダイレクトに移動できる経路についての情報だけが与えられているのです。ただ、これは逆に言うと、次の様な条件付きの問題は簡単に解けるということです。[例題1] N ノード、M リンクの有向グラフ G があり、G は有向閉路を含みません。各リ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fenakai00.hatenablog.com%2Fentry%2F2021%2F07%2F16%2F193841" title="G - Longest Path の解説（その1） - めもめも" 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 19:38:41 rich https://enakai00.hatenablog.com/entry/2021/07/16/193841 1.0 100%