負閉路
AtCoder
AtCoder500点
ABC-E
青色diff
Union-Find
重み付きUnion-Find
データ構造
グラフ
負閉路
グラフのconnectivity
最短路問題
牛ゲー
双対性
クエリ処理問題
クエリ(グラフ上)
前処理
解空間:O(N^2)通りの選択肢
最長路問題
NP困難(特殊構造なので解ける)
重み付き Union-Find が使える鮮やかな楽しい問題! 問題へのリンク 問題概要 頂点数 (頂点番号が ) のグラフが与えられる。このグラフには 組の辺があり、 組目の辺は、 頂点 から頂点 へと、長さ の有向辺 頂点 から頂点 へと、長さ の有向辺 となっている…
AtCoder
ABC-D
グラフ
Bellman-Ford法
最短路問題
AtCoder400点
負閉路
コーナーケース
青色diff
けんちょん本演習問題
【問題集】最短路問題
そのまま覚えたいシンプル設定の中堅以上の典型問題
そのまま覚えたい典型問題
Bellman-Ford 法を活用する典型問題ですが、少し注意が必要な問題ですね。 問題へのリンク 問題概要 頂点 辺の重み付き有向グラフが与えられます。 頂点 から頂点 へと至る最長路の長さを求めてください。 ただし、いくらでも長い路が存在する場合は inf と…