第六回アルゴリズム実技検定 G問題 - 競技プログラミング日記

辿り着く事のできる頂点は単調増加．よって，前日までの結果との差分を計算して高速化したい．一度調べ終わった頂点，辺はもう一度調べる必要は無さそう．

新たに追加される頂点 \(v\) の入れ物
新たに追加される辺 \(e\) の入れ物

を用意しておけば良い感じ．ただし，辺はコストが \(x_{i}\) 以下である必要がある．それを高速に取り出すために，priority_queue を使っておくと良さそう．とりあえず，辿り着いた頂点 \(v\) から出ている辺 \(e\) を，使える候補として priority_queue に入れておく．そして， \(x_{i}\) 以下のものだけ実際に使う．
単調性

一度追加された辺の候補は，次の日以降も使える候補に入っている
一度追加された辺(頂点)は，次の日以降も使える辺(頂点)に入っている

という単調性が重要．

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

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

int main() {
  ll n, m, q;
  cin >> n >> m >> q;

  vector<vector<tuple<ll,ll>>> gr(n);// cost, vx
  rep(i,m){
    ll a,b,c; cin >> a >> b >> c;
    --a, --b;
    gr[a].emplace_back(c,b);
    gr[b].emplace_back(c,a);
  }

  queue<ll> qv;
  vector<bool> used(n);
  ll ans = 0;
  min_priority_queue<pll> qe;

  qv.push(0);
  used[0] = true;
  ans++;
  rep(i,q){
    ll x ; cin >> x;

    while(qv.size()){
      ll cv = qv.front(); 
      qv.pop();

      for(auto [cost, nv]: gr[cv]){
        qe.push({cost, nv});
        
      }
    }

    while(qe.size()){
      auto [cost, nv] = qe.top(); 
      
      if(cost <= x){
        qe.pop();

        if(!used[nv]){
          qv.push(nv);
          used[nv] = true;
          ans++;
        }
      }else{
        break;
      }
    }

    cout << ans << endl;
  }

  return 0;
}