AtCoder ABC 164 E - Two Currencies (500 点)

これ、頂点を倍加してダイクストラする系。問題へのリンク問題概要頂点辺の連結な無向グラフが与えられる。各辺には通行に要する料金円 (所持金が以上でなければ通行できない) 通行に要する所要時間秒という属性がある。また、各頂点では所持金を…

Codeforces Round #616 (Div. 1) C. Prefix Enlightenment (R2400)

Codeforces Union-Find木重みつきUnion-Find木クエリ処理問題各kに対してパリティグラフの頂点を倍加する二部グラフ差分更新クエリ先読みデータ構造差分制約系 DFS 木DP DP

Union-Find を使いこなす！！！問題へのリンク問題概要 (意訳) 個の 0-1 変数が与えられていて、最初はそれらの値について特に制約はない。いま、個の制約が順に与えられる。各制約はそれぞれ 1 つの変数と 0 か 1 の値 w を指定して、とする 2 つの変…

AtCoder AtCoder500点 ABC-E BFS 最短路問題グラフ問題グラフの頂点を倍加する最小回数最小コスト

こういうのを僕が初めて解いたのは、はまづさんのこの問題だった。 atcoder.jp そして、昔の ICPC などでは特に、この手の問題は何度も何度も出題されていた。問題へのリンク問題概要頂点辺の有向グラフが与えらえる。頂点から頂点へと、けんけんぱで…