Internet Problem Solving Contest

• Correct output – C1
• Correct output – C2
• C program solving both data sets

The problem can be represented as a graph in which vertices correspond to cities and edges correspond to phone lines. In this representation, the problem can be formulated as follows:

We are given an N×N matrix A of positive numbers and a positive integer E (in fact, we are given just half of A, but the matrix is symmetric and all elements on the diagonal are unimportant). We have to determine, whether it is possible to find a graph with N vertices and E edges (each edge must have a positive length) that satisfies the condition C: "matrix element A[I,J] is the length of shortest path beween vertices I and J".

We will try to find a graph G satisfying C with the least number L of edges. It is clear that once this is done it is possible to add more edges with really large weights without changing the lengths of shortest paths. Thus the answer is "YES" for all values of E between L and N*(N-1)/2.

Our algorithm works like this:

1. If E>N*(N-1)/2, answer "NO" (trivial condition)
2. Start with an empty graph G on N vertices.
3. Process elements of A[I,J] in increasing order:
   • Find the length D of the shortest path between I and J in G (our implementation uses Dijkstra's shortest-path algorithm)
   • If D<A[I,J], output "NO" and stop
     If D>A[I,J], add an edge between I and J of length A[I,J] to G
     If D=A[I,J], do nothing
4. If the resulting graph G has more than E edges, answer "NO", otherwise answer "YES"

Clearly, this algorithm runs in O(N⁴) time and O(N²) space.

Correctness of the algorithm

Denote G_S a graph that is obtained by our algorithm just after processing all entries of A[i,j]≤S. We will show that each graph G_S has the following two properties:

• P(S): "If A[I,J]≤S, then the length of the shortest path between I and J in graph G_S is A[I,J]"
• L(S): "G_S contains only edges which are present in all graphs satisfying property P(S)".

Clearly, if Q is the largest element in matrix A, then P(Q) is exactly the property C, and L(Q) implies that G_Q has the least possible number of edges. In other words, graph G_Q, obtained when our algorithm is finished, indeed satisfies the requirements of the problem.

We will prove our claim by induction on S (where S is a value taken from the matrix A or 0). Base case: Graph G₀ has no edges. Clearly, this graph satisfies property P(0) and L(0).

Inductive step: Assume that graph G_S' satisfies P(S') and L(S') and let S be the smallest entry from A larger than S'. We will show that G_S also satisfies properties P(S) and L(S).

We obtained graph G_S by adding several edges of weight S to graph G_S'. An edge was added between pair of vertices I,J if and only if A[I,J]=S, and the length of the shortest path between I and J in G_S' was longer than S. Since G_S' satisfies P(S'), it is easy to see that G_S must satisfy P(S).

It remains to show that G_S also satisfies L(S). Let us assume that there is an edge (I,J) in G_S such that there exists a graph H satisfying P(S) where I and J are not connected.

• If A[I,J]<S, then the edge (I,J) was already present in G_S'. However, H also satisfies P(S'), and therefore (according to induction hypothesis L(S')) it must contain all edges of G_S', which is a contradiction.
• If A[i,j]=S, then the shortest path from I to J in graph H must contain at least one internal vertex K. Then, A[I,K]<S and A[K,J]<S (or equivalently stated as A[I,K]≤S' and A[K,J]≤S'). This means, that the corresponding paths from I to K and from K to J were already present in G_S'. Consequently, the path I to J of length S was also included in G_S' and our algorithm could not add the edge (I,J) to G_S, which is a contradiction.

Thus, G_S satisfies L(S).

We have proved that if the algorithm produces graph G_Q, the graph satisfies properties P(Q) and L(Q). It is also possible that the algorithm will fail while producing graph G_S from G_S'. This is because the for some edge (I,J), the graph G_S' already contained a path shorter than A[I,J]. Property L(S') implies that the correct answer is indeed "NO" in this case.