この記事は、競技プログラミングでよくあるグラフの問題で、愚直に問題文の指示通りやると辺の数があまりにも多くなりすぎるようなものに対して、コスト0の辺をうまく利用することで辺の数のオーダーを落とす者である。 性質上、すべてのものに適応できるわ…
atcoder.jp 概要 最大10^5個の頂点(それぞれ1~Nまで番号を振る)を持つ辺に次の最大10万個のqueryで無向辺を追加する。クエリ LとRとCを与えられる。を満たすすべての(a, b)の間にコストCの辺を張る。クエリを全部処理したのち、頂点1から頂点Nまでの最短経路…
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。