mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ いやなんか時間とってゆっくり競プロやりたいんですけど… 問題 codeforces.comコスト付きの無向グラフが与えられる。いくつかの辺のコストは好きに選べるので, s から t への最短経路の大きさを L にしたい。このようなことが可能であれば, そのうちの 1 つを答えよ。 解法 まず自明に解がない場合を省きます。というのは, いじれるすべての辺のコストを INF にしても最短経路が L 未満の場合と, いじれるすべての辺のコストを 1 にしても最短経路が L より大きい場合です。逆に, これ以外の場合は, 解が存在することが示せます。これは いじれるすべての辺のコストを 1 にすると最… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F09%2F20%2F215821" title="Codeforces Round #372 (Div. 1) B. Complete The Graph - mayoko’s diary" 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 2016-09-20 21:58:21 rich https://mayokoex.hatenablog.com/entry/2016/09/20/215821 1.0 100%