グラフ理論ではないしグラフですらない。列。 解法 両端にダミーの頂点を追加すると、操作 は操作 で表現できる。 よって操作 だけを考えればよい。 最初の頂点も操作 で作ることにすれば、問題は以下のように言い換えられる。 頂点 つが辺で結ばれている。 …

問題設定 無向グラフ , 非負の辺重み , 始点 , 終点 が与えられる。 各 について、 上での 最短路長を求めよ。 この問題を の時間計算量で解くアルゴリズムを説明する。 本質的に同じ問題が https://codeforces.com/contest/1163/problem/F で出題されており…