PAST #9: 第九回 アルゴリズム実技検定 I - 直通エレベーター を解いた。

解いたときに考えたことを書く。

問題: https://atcoder.jp/contests/past202112-open/tasks/past202112_i

グラフの最短経路の問題。エレベーターの止まる階以外は階段で到達しても次の階に移動するだけなので頂点として持たなくて良い。 N <= 10^18 なので素朴には持てないので座標圧縮する。 M <= 10^5 なので座標圧縮すれば持てる件数になる。

エレベーターの移動を辺で表すほか階段の移動を辺で表す必要がある。前後の (エレベーターの止まる) 階への移動ができれば十分なので頂点をソートして前後の階にも辺を貼っておく。

あとはダイクストラ法で解ける。

提出: https://atcoder.jp/contests/past202112-open/submissions/30741122 解説: https://atcoder.jp/contests/past202112-open/editorial/2435

王子動物園の夜桜通り抜けに行った。子どもを連れて行くと疲れる。まだワクチン接種の副反応で体がだるい。

今日のコミット。

• rust-examples 1 commit
  • update clap1
• rust-atcoder 1 commit
  • past202112-open i