第九回 アルゴリズム実技検定 I問題

PAST009I

階は \(N \leq 10^{18}\)個と多く，エレベーターは \(M \leq 10^{5}\) 個と少ないので， エレベーターから考える． 最短経路問題と同じになる． エレベーターの始点，終点になっている階と， \(1,N\) 階のみ頂点としたグラフを考える．

• 階を小さい順で並べた時，隣同士の階は辺で結ぶ． コストは階の差の絶対値．
• エレベーターのある階層どうしは，与えられたコストで張る．

あとはDijikstra.

実装
階層は大小だけが重要なので，座標圧縮する．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n, m, k, q;

  cin >> n >> m;

  Points<ll> p;

  ll mi = INFL, ma = -INFL;

  vector<tuple<ll,ll,ll>> ary;

  rep(i,m){

    ll a,b,c ; cin >> a >> b >> c;

    --a, --b;

    p.add(a);

    p.add(b);

    chmin(mi, a);

    chmax(ma, b);

    ary.emplace_back(a,b,c);

  }

  ary.emplace_back(0, mi, abs(mi));

  ary.emplace_back(ma, n-1, abs(n-1-ma));

  p.add(0);

  p.add(n-1);

  p.init();

  rep(i,p.size()-1){

    ary.emplace_back(p[i], p[i+1], abs(p[i] - p[i+1]));

  }

  digraph<ll> g(p.size());

  for(auto [a,b,c]: ary){

    c = min(c, abs(b-a));

    g.add(p(a), p(b), c);

    g.add(p(b), p(a), c);

  }

 

  vll dis = dijkstra(g, p(0));

  cout << dis[p(n-1)] << endl;

  return 0;

}