AtCoder Beginner Contest 192E

ABC192E

コストが特殊な Dijikstra. 時刻を距離の代わりとして保持しておき， 時刻が \(k\) の倍数になるまで待機してから移動すればよい． 現時点の後ろの，一番近い \(k\) の倍数で移動するのが最善．

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

struct EDGE{

  ll to, k, t;

  EDGE(){}

  EDGE(ll to, ll k, ll t): to(to), t(t), k(k){}

};

int main() {

  ll n, m , x, y;

  cin >> n >> m >> x >> y;

  --x, --y;

  vector<vector<EDGE>> g(n);

  rep(i,m){

    ll a,b,t,k; cin >> a >> b >> t >> k;

    --a, --b;

    g[a].push_back(EDGE(b, t, k));

    g[b].push_back(EDGE(a, t, k));

  }

  vector<ll> dis(n,INFL);

  min_priority_queue<pll> q;

  dis[x] = 0;

  q.push({0,x});

  while(q.size()){

    auto [cd, cv] = q.top(); q.pop();

    if(dis[cv] != cd) continue;

    for(auto [nv, nt, nk]: g[cv]){

      ll nd = cd;

      nd = ceil(cd, nk)*nk;

      nd += nt;

      if(chmin(dis[nv], nd)){

        q.push({nd, nv});

      }

    }

  }

  ll ans = dis[y];

  if(ans >= INFL) ans = -1;

  cout << ans << endl;

  return 0;

}