第三回 アルゴリズム実技検定 M - 行商計画問題
$ k \le 16と小さいのでスタート地点と取引をする町の間のそれぞれの距離が分かれば循環セールスマン問題の様に解ける
ある町からの他全ての町への最小距離は道のコストが全て1円なのでBFSで$ O(M)で求められる
これをスタート地点と取引をする町から実行すれば良い
計算量は$ O(KM + 2^k k^2)
問題: https://atcoder.jp/contests/past202005-open/tasks/past202005_m
提出: https://atcoder.jp/contests/past202005-2/submissions/13768526
#第三回アルゴリズム実技検定 #アルゴリズム実技検定 #M #AtCoder