https://atcoder.jp/contests/abc035/tasks/abc035_d
- 考えたこと
- T分間最初の街に留まってA1を貰い続けるより、移動コストを払って他の街に行った方が得なことがある
- この時、移動先の街の方がAiが大きくなければ得にはならない
- 移動した街からさらに移動する場合、途中の街に留まることは最適解にならない
- よって「最短距離で街iに言って時間を過ごして戻ってくる」が最適解、どのiが正解かを調べる
- 最初にダイクストラ法で各街への最短距離を求める
- スコア最大のものを選ぶ
- 公式解説
- WA: 問題条件勘違い、道が双方向ではない
- 帰り道が単一始点ではない
- →辺を反転してダイクストラ法をすれば単一終点の最短経路もできる