Sum of all pairs' shortest path

Правка en2, от Minh639, 2024-05-13 15:03:48

You are given a weighted undirected graph consisting of n vertices and m edges ($$$1 \leq n, m \leq 10^5$$$). Let $$$d(u, v)$$$ be the shortest distance between $$$u$$$ and $$$v$$$. What is the best algorithm to calculate $$$\sum_{1 \leq u < v \leq n} d(u, v)$$$?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Minh639 2024-05-13 15:03:48 10 Tiny change: 're given an undirecte' -> 're given a weighted undirecte'
en1 Английский Minh639 2024-05-13 13:32:35 266 Initial revision (published)