A Question about shortest path....

Правка en1, от Phuong0703, 2022-12-25 05:14:05

So I have been asking myself for a long time these 2 problems:

- Given a graph with N vertices and M edges, find the sum of all shortest paths between (u -> v)

- Given a graph with N vertices and M edges, answer queries asks for the shortest path between (u -> v)

It is guaranteed that there exists a way to travel from nodes to others.

Constraints: N <= 1e5 , M <= 1e5 , Q <= 1e5(Q is number of queries for the second problem)

Since then, I have been thinking and searching but nothing comes out good enough to pass the constraints.

Is there any way to solve these?

Теги shortest path, graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Phuong0703 2022-12-25 10:52:02 19
en1 Английский Phuong0703 2022-12-25 05:14:05 630 Initial revision (published)