atcoder_水色精進記録17_ABC335e

Atcoder水色精進記録

ABC335
E - Non-DecreasingColorfulPath
https://atcoder.jp/contests/abc335/tasks/abc335_e

アルゴリズム・データ構造

ダイクストラ

考察

Sが広義短調増加である必要があるため
u,vが与えられた時に、
A[u]<=A[v]の時は、u->vのpathを追加
A[v]<=A[u]の時は、v->uのpathを追加
上記は排他ではなく、並列で確認
とすれば、無効な辺は考えなくて良くなる。

BFS,DFSで全てのpathを全探索すると計算量がオーバー

現在いる頂点より低い頂点に訪れることはできない
頂点が低い順にpathを確定すれば良さそう
→頂点の重さをkeyとしてダイクストラ的な順番で計算すれば求められる

提出

感想

ダイクストラが久々だったが、実装を空で書くことができた。