最短経路問題

AtCoder Beginner Contest 051: Candidates of No Shortest Paths

問題 問題文 https://atcoder.jp/contests/abc051/tasks/abc051_d 問題概要 頂点数 N, 辺の数 M の重み付き無向グラフが与えられる. ただし, このグラフは自己ループと二重辺をもたず, 連結であるものとする. 任意の 2頂点間のどの最短経路にも含まれない辺…

ABC070: D - Transit Tree Path

問題 問題文 https://beta.atcoder.jp/contests/abc070/tasks/abc070_d 問題概要 頂点数が N の重み付き無向グラフが与えられる。 与えられるグラフは辺の数が N−1 本で閉路のない連結グラフ, すなわち木構造となっている。 頂点 から 頂点 K を経由しつつ, …