問題一覧 > 通常問題

No.2200 Weird Shortest Path

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 : stoqstoq / テスター : misty1999misty1999
3 ProblemId : 8148 / 自分の提出
問題文最終更新日: 2023-01-26 18:52:58

問題文

$N$ 頂点 $M$ 辺の単純かつ連結な無向グラフがあります。

各辺には重みという非負整数のパラメータが設定されています。 $i$ 番目の辺は頂点 $a_i,b_i$ を双方向に結び、重みは $w_i$ です。

頂点のペア $(u,v) \ (u < v)$ のコストを、頂点 $u$ から頂点 $v$ に向かうパス全てを考えたときの、「パスに含まれる辺の重みの最大値」の最小値と定めます。

全ての異なる $2$ 頂点のペア $(u,v) \ (1 \leq u < v \leq N)$ に対するコストの総和を求めてください。

入力

$N\ M$
$a_1\ b_1\ w_1$
$\vdots$
$a_M\ b_M\ w_M$

  • 入力は全て整数
  • $2 \leq N \leq 10^5$
  • $1 \leq M \leq 2 \times 10^5$
  • $1 \leq a_i < b_i \leq N$
  • $1 \leq w_i \leq 10^8$
  • 与えられるグラフは単純かつ連結

出力

全ての異なる $2$ 頂点のペア $(u,v) \ (1 \leq u < v \leq N)$ に対するコストの総和を出力してください。

サンプル

サンプル1
入力
4 5
1 2 1
1 3 2
1 4 3
2 3 4
3 4 5
出力
14

グラフは次のようになります。

例えば $2$ 頂点 $(2,3)$ のコストは、$2 \rightarrow 1 \rightarrow 3$ というパスが重みの最大値を最小化するので $2$ です。

コストの総和は $14$ です。

サンプル2
入力
10 16
9 10 8
4 8 16
1 5 19
6 7 16
6 10 4
7 10 5
2 4 19
3 10 19
2 5 13
1 6 9
8 10 20
4 6 13
3 6 5
3 5 1
6 9 6
5 10 6
出力
468

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。