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 ofall 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?↵
↵
↵
**- Given a graph with N vertices and M edges, find the sum of
↵
**- 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?↵
↵
