yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ 久しぶりですごい時間がかかったのでメモ 大体次の問題。 $N$ 頂点 $M$ 辺の有向グラフと非負整数 $K$ が与えられる。各辺には非負整数の重みが付いていて、辺 $e$ の重みを $d_e$ とする。$K$ は $1 \to N$ の最短距離より小さくない。 $1$ 円払うと好きな辺の重みを $1$ 増やせる時、頂点 $1$ から $N$ の最短距離を $K$ にするために必要な最小コストは？ 構築あり: 各辺について何回伸ばすかも復元する必要あり まず、この問題はほぼ最小費用循環流の双対問題そのものなので、構築がなければ難しくない。というか大体コレ J - Longest Shortes… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2023%2F11%2F27%2F230816" title="UCUP 2-11 (Nanjing) E: Extending Distance / 最小費用流の双対 - よすぽの日記" 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 2023-11-27 23:08:16 rich https://yosupo.hatenablog.com/entry/2023/11/27/230816 1.0 100%