コストが変則な Dijikstra. 時刻 \(t\) に 頂点 \(v\) を出発すると，次の頂点に到達する時刻が \(f(t) := c + \lfloor d/(t+1) \rfloor\) となる． 出発するときに待てば良いので，それ以外のタイミングで待つ必要はない．
簡単のため floor を無視して考えると， およそ \(sqrt(d)\) の前後で \(f(t)\) は最小となる． \(v\) に到達した最小の時刻を \(t_{0}\) とすると， \(f(t)\) が最小となる \(t\) の候補は，十分大きな定数 \(Y\) に対して \(t = t_{0}\) または \(max(sqrt(d) - Y, t_{0}) \leq t \leq sqrt(d) + Y\) のどれか． これを全探索すれば良い．
実装
変数に似た名前を使うときは注意．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n >> m;
vll a(m), b(m) , c(m), d(m);
rep(i,m){
cin >> a[i] >> b[i] >> c[i] >> d[i];
a[i]--, b[i]--;
to[a[i]].emplace_back(b[i], c[i], d[i]);
to[b[i]].emplace_back(a[i], c[i], d[i]);
}
min_priority_queue<pll> q;
vll dis(n, INFL);
q.push({0,0});
chmin(dis[0], 0LL);
while(q.size()){
auto [cdis, cv] = q.top(); q.pop();
if(dis[cv] != cdis) continue;
for(auto [nv, nc, nd] : to[cv]){
ll ndis = cdis + nc + nd/(cdis+1);
ll sq = sqrt(nd);
ll C = 100;
srep(i, sq-C, sq+C+1) if(i >= cdis){
chmin(ndis, i + nc + nd/(i+1));
}
if(chmin(dis[nv], ndis)){
q.push({ndis, nv});
}
}
}
ll ans = dis[n-1];
if(ans >= INFL) ans = -1;
cout << ans << endl;
return 0;
}
