Recently my friend told me about the following problem. We are given connected undirected weighted graph with *n* ≤ 100000 vertices and *m* ≤ 400000 edges. Now we have to answer *q* ≤ 2500 queries. In each query you have to find shortest path between given pair of vertices.

I am curious how to solve this problem efficiently. Obviously we can run Dijkstra algorithm *q* times, but on a such a big graph I suppose this will be too slow. The only speedups I came up with are:

- Meet in the middle technique. For each query we can run Dijkstra algorithm from source and target vertex and stop after finding the first path.
- After running Dijkstra search for answer to the other queries in tree of the shortest paths.

I believe that in pessimistic case they will be as slow as naive solution.

Do you know any faster solution?

Auto comment: topic has been updated by m.boniecki (previous revision, new revision, compare)._ We are given connected undirected weighted graph_

If your graph is acyclic, sure, we can do better.

OMG LTDT is back!

It's not acyclic.

In the general case there's no solution. However, I do remember an extremely similar problem where it was given that the answer for all queries would be greater than some large number (think $$$N/10$$$). That's probably where your friend got it from. I can't find the original problem, but it was in some OI contest.

It may have been a XXVI polish OI https://szkopul.edu.pl/problemset/problem/QHh99tBu4p9FMsFohv4da7S7/site/?key=statement