abc035_d
考えたこと
T分間最初の街に留まってA1を貰い続けるより、移動コストを払って他の街に行った方が得なことがある
この時、移動先の街の方がAiが大きくなければ得にはならない
移動した街からさらに移動する場合、途中の街に留まることは最適解にならない
よって「最短距離で街iに言って時間を過ごして戻ってくる」が最適解、どのiが正解かを調べる
最初にダイクストラ法で各街への最短距離を求める
スコア最大のものを選ぶ
公式解説
WA: 問題条件勘違い、道が双方向ではない
帰り道が単一始点ではない
→辺を反転してダイクストラ法をすれば単一終点の最短経路もできる
Related Pages
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
- →past5×past202012×アルゴリズム実技検定×past過去問練習202012×past5e×past5f×past5g×past5h×PAST5I×past5j×past5k×past5l×past5m×past5n×past5o×番兵×地図読み込み時に番兵をつける×ゴールをスタートにする×ゴールを一つにする×ダイクストラ法×bit_dp×期待値dp×二次元の片方を時間軸にする×past2n→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]