Tima3's blog

By Tima3, 15 months ago, In English

Hello codeforces

Recently I met with several tasks (in my head) and could not come up with a solution.

1 Given a graph consisting of undirected weighted edges. There are two types of queries, add an edge to a graph. Find the shortest path between two vertices.

As I understand it, if it were said that a lot of trees were given, the task would be solved using DSU or Link-cut tree, but with graphs it becomes much more difficult, and the question is whether there is something better than running Dijkstra for every request of the second type.

2 Given a directed graph and queries of 2 types. 1 — add a directed edge to the graph 2 — tell if there is a path between two vertices

  • Vote: I like it
  • +35
  • Vote: I do not like it