Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

RestingRajarshi's blog

By RestingRajarshi, history, 7 years ago, In English

I have a undirected graph, with 0/1 edge cost. The graph is a complete graph. I have two operations: -- update: flip the edge cost of a particular edge. that is, if it's cost was 0, make it 1, or vice versa. -- query: shortest path between the source and target vertex.

We are given the graph as a adjacency matrix, as well as the source and the target node in the input. The source and the target node remain fixed. Expected memory is o(n^2) (obviously) and time complexity is o(logn) for both update and query.

Thanks for any help in advance.

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