Faster way to recalculate maximum distance in graph

Question

Assume you are given a weighted directed graph G = (V, E) with n nodes, p of which are central. Let C, |C| = p be the set of central nodes and N = V \ C be the set of non-central nodes. The value of edge e_ij is finite non-negative real number if:

1. i is from the set N, while j is from the set P, or
2. i is from the set P, while j is from the set P, or
3. i is from the set P, while j is from the set N.

Otherwise, if i is from the set N and j is from the set N, value of e_ij is equal to positive infinity.

We are interested in finding maximum over all shortest distances in graph G. The fastest algorithm I found to solve this is using a simple modification of Floyd-Warshall's algorithm, which runs in O(n²p). Here is the simple pseudo-code:

FOR ALL k FROM the set C DO
  FOR ALL i FROM the set V DO
    FOR ALL j FROM the set V DO 
      e[i, j] = MIN(e[i, j], e[i, k] + e[k, j])
-----------------------------------------------
result = 0
FOR ALL i FROM the set V DO
  FOR ALL j FROM the set V DO
    result = MAX(result, e[i, j])
-----------------------------------------------
RETURN result

Probably, there is no faster algorithm than that. (Or, am I wrong? :))

However, I'm more interested in the following, and I think there is something faster here. Assume that we simply exchange two nodes from the sets C and N, ie. for some v_c from C and some v_n from N, the set C becomes C + v_n - v_c and set N becomes N + v_c - v_n. Now, we are interesting in finding new maximum distance over all shortest distances in G.

The faster algorithm I know is simply to calculate from the beginning new maximum distance using described Floyd-Warshall's method, which runs again in O(n²p). Is there any faster method for calculating this that probably uses the old calculated values of shortest distances before exchanging nodes?