2019-06-19から1日間の記事一覧
問題概要 頂点辺の重み付き無向連結グラフの任意の全ての2頂点間の最短経路に含まれない辺の総数を求めよ。 atcoder.jp 解法 頂点間の最短経路に頂点を結ぶ辺が含まれるためには、を満たす必要がある。これは感覚的にも分かりそうだし証明は割愛。 ここまで…
問題概要 頂点辺の重み付き無向連結グラフの任意の全ての2頂点間の最短経路に含まれない辺の総数を求めよ。 atcoder.jp 解法 頂点間の最短経路に頂点を結ぶ辺が含まれるためには、を満たす必要がある。これは感覚的にも分かりそうだし証明は割愛。 ここまで…