blog.bouzuya.net

2022-04-08 PAST #9 K - ガソリンスタンド を解いた

PAST #9: 第九回 アルゴリズム実技検定 K - ガソリンスタンド を解いた。

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

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

最短経路問題。 Q 個のクエリについて 2 点間の最短経路の長さを求める。ただし K 個の指定された頂点 a から 1 個以上を通らないといけない。

K <= 20 と小さいので K 個の a の各頂点から他のすべての頂点に対しての最短経路の長さを事前計算できる (dist[i][j] := a_i から頂点 j への最短経路の長さ) 。あとは MIN(dist[x][s_i] + dist[x][t_i]) をクエリごとに調べれば良い。

ある頂点を経由する経路として dist[s][k] + dist[k][t] のような求め方をするのはワーシャルフロイド法を含めてよく出てくる。それと K <= 20 の制約を見れば間に合うことに気づける。

解説を見て気づいたこととしてぼくはダイクストラで最短経路を求めたのだけどこの問題なら BFS でも良かった。

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

『のび太のねじ巻き都市冒険記』を観た。

今日のコミット。