Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Sarutobi_Messi's blog

By Sarutobi_Messi, history, 6 weeks ago, In Russian

Вам дан неорентированный взвешанный связанный граф из n вершин и m ребер. Назовем стоимостью пути значение максмимума среди весов ребер на пути. Пусть d(v,u) – это минимальная стоимость пути начинающегося в v и заканчивающегося в u. Посчитайте значение ∑1≤v<u≤nd(v,u) – сумма d(v,u) по всем парам (v,u).

В первой строке даны числа n(2≤n≤10^5) и m(n−1≤m≤3⋅10^5 – количество вершин и количество ребер.

В следующих m даны si, ti, wi(1≤si,ti≤n,1≤wi≤10^6) – описание ребра соеденяющего вершины si и ti с весом wi. Гарантируется что si≠ti.

Гарантируется что от каждой вершины можно добраться до любой другой двигаясь по рербам графа.

  • Примеры
  • входные данные
  • 3 3
  • 1 2 5
  • 1 3 1
  • 2 3 4
  • выходные данные
  • 9
 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it