emtubasa https://blog.hatena.ne.jp/emtubasa/ ツバサの備忘録 https://emtubasa.hateblo.jp/ ダイクストラ法 問題 提出コード 解法 頂点を増やします。 都市に着いた段階で予算のうちだけ消費するような経路の中で、襲われる人数の最小値 とすると、今いる都市、消費した予算、襲われる人数を一緒に持った状態でダイクストラ法を適用すれば良いです。 次の都市に遷移する際に、予算を消費するか、消費せずに襲われる人数を増やすかの2択が発生するので、それぞれについての遷移を考えていけばいいことになります。 感想 最初、無条件で予算を消費しつつ襲われる人数をカウントしていく問題だと誤読したので、サンプルが全く合わずに混乱していました… 頂点を増やしてダイクストラを行う問題、やはり多いですね。 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Femtubasa.hateblo.jp%2Fentry%2F2019%2F07%2F01%2F172908" title="AOJ 2151 - 勇敢なお姫様またも現る - ツバサの備忘録" 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.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2019-07-01 17:29:08 rich https://emtubasa.hateblo.jp/entry/2019/07/01/172908 1.0 100%