URAL 1770 - The Party of Ural Champions

A useful observation: The original graph can be obtained from removing some edges from the given distance matrix. Futuermore, if d[i][k]+d[k][j] = d[i][j], then edge (i → j) may be removed.

My solution used Reversed Floyd-Warshall algorithm. The basic idea is like

for k=1 to n
  for i=1 to n
    for j=1 to n
      if d[i][k]+d[k][j]==d[i][j] then d[i][j]=INF

However, the problem do not allow directional edge, so we need to avoid setting d[i][j]=INF but keeping the edge (j → i). To solve this problem, I used the following method:

for k=1 to n
  for i=1 to n
    for j=1 to n
      if d[i][k]+d[k][j]==d[i][j] AND r[j][i] then d[i][j]=d[j][i]=INF
      else if d[i][k]+d[k][j]==d[i][j] then r[i][j]=1

At last, don't forget to see if the input matrix satisfy triangular inequality