ABC180 E - Traveling Salesman among Aerial Cities (500)
各都市を一度以上通ってとあるが、移動コストの計算方式から同じ都市を二度通って全ての都市を一度だけ通る場合よりコストが減ることが無いので全ての都市を一度だけ通れば良い
全ての都市を一度ずつ通るのは巡回セールスマン問題と同様に解ける
$ dp[これまでに通った都市の集合][最後にいる都市]
とすればよい
DPがボトルネックで
$ O(2^N N^2)
問題:
https://atcoder.jp/contests/abc180/tasks/abc180_e
提出:
https://atcoder.jp/contests/abc180/submissions/17458661
#ABC180
#500pt
#E
#ABC
#AtCoder
#TSP