JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ ワーシャルフロイド ABCのF問題 ABC本番で敗北した問題 本番でのACには至らなかったが、どうやらグラフに対して「特定の辺を削除する」または「指定した2頂点間を移動する際の最短距離を答える」クエリがたくさん飛んでくる系統の問題は典型らしいのでこの一問でしっかりと固めたいと思う。 ↓問題のページ↓ F - Road Blocked 辺を削除するクエリが飛んでくる可能性があるという話を一旦忘れてみる。頂点数が\(N\)の単純グラフで、どの辺も必ず正の重みを持っているという状況であり、制約を確認すると、\(N\)は最大でも\(300\)とかなり小さめである。このような場合にはワーシャルフロイド法を利用して、すべての頂点対に関しての最短距離を求める手法が非常… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2024%2F10%2F14%2F211901" title="ABC375 F - Road Blocked - JunKobayashi&#39;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 2024-10-14 21:19:01 rich https://junkobayashi.hatenablog.com/entry/2024/10/14/211901 1.0 100%