[問題案] Shortest Path on Treewidth 2 Graph

[yosupo06]

問題ID: shortest_path_on_treewidth_2_graph 問題名: Shortest Path on Treewidth 2 Graph

想定アルゴリズム: 木分解 -> Balanced Separator -> Dijkstra

問題概要

N頂点の非負の重み付き有向グラフが与えられます。各辺を無向辺としてみた時、このグラフは木幅2です。

Q個のクエリが飛んできます。各クエリは

• given u, v : uからvへの最短経路の長さを出力

入力

出力

制約

N, Q <= 200,000

[yosupo06]

O(N log^2 N + Q log N)なのでQ多くていいかも

[yosupo06]

タイトルの英文わからねえ　on / in ?

[maspypy]

全然知らない話だけど問題を作るのは作って良さそうに思います。 資料とかあれば貼っておいてもらえるといいと思います。