JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ 多始点BFS 超頂点 基礎から徹底 ↓問題のページ↓ C - Humidifier 3 ※特に断らない限り、0-indexedを前提に記載する。 なんとか本番ACには成功したが、超頂点を利用すると鮮やかに多始点BFS問題をしばき倒すことができる感覚が確立されておらず、このままでは解説を読んで「なんて賢い手法なんだ」と感動したという記憶以外が残らない気しかしないのでまとめておく。 重みのないグラフについて、「特定の一頂点からの最短距離を全ての頂点に対して求めろ」と言われればさすがに幅優先探索で一撃だというのは感覚としても身に着いているが、本問における「加湿器が置かれている場所」のように、「始点となる条件を満たしている頂点が複数個存… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2024%2F12%2F10%2F222109" title="ABC383 C - Humidifier 3 - 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> https://cdn-ak.f.st-hatena.com/images/fotolife/J/JunKobayashi/20241210/20241210215707.png Hatena Blog https://hatena.blog 2024-12-10 22:21:09 rich https://junkobayashi.hatenablog.com/entry/2024/12/10/222109 1.0 100%