I heard about the following problem in a competitive programming camp:
Given an undirected weighted graph $G$ with one vertex initially.
Suppose you are given two types of queries:
Add a new vertex to $G$ with some undirected weighted edges between this vertex and subset of vertices added previously to $G$ in time complexity $O(n^2)$, where negative weights are allowed.
Find the length of the shortest path between two vertices in $O(1)$.
Note: Floyd Warshall's algorithm is $O(n^3)$ for each query of type 1.
I'm looking for (in addition to your answer):
Any useful reference to solve such a problem.
Links for similar problems in online judges (Codeforces, SPOJ .. etc).