2017-09-27から1日間の記事一覧

AIM Tech Round 4 (Div. 1) D. Dynamic Shortest Path

問題 http://codeforces.com/contest/843/problem/D 解法 最初にダイクストラで距離を求めておき、各クエリごとにダイクストラで追加で増えた分の距離を計算して加算していく。各クエリごとに距離は 1 しか増えないので、キューを距離の数だけ用意すれば、ク…

会津合宿 2017 2 日目 G : Picnic

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day2&pid=G 解法 ワーシャルフロイドと巡回セールスマン問題の bit DP で、ある町の部分集合を回って戻ってくるのにかかるコストを前計算しておく。さらに、町の集合を の 2 つに…