A Question about shortest path....
Difference between en1 and en2, changed 19 character(s)
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) for every 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?↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Phuong0703 2022-12-25 10:52:02 19
en1 English Phuong0703 2022-12-25 05:14:05 630 Initial revision (published)