Don't understand - the algorithm is just Floyd, and so few people solved this problem...

Do you think I understand why I have WA#6?

I had WA6 when I spread minimum over inner houses to all others (including outer). This is wrong, you should consider only outer house as a new inner one. But now I have WA16 :)

Edited by author 27.08.2008 11:19

WA16 was that I added roads leading from some house to itself as such road for every house. This is also wrong.

I start my solving with two hypotheses:
1. It is enough to use only one inner room.
2. Using this room it is enough edges between two rooms inner and outer consider as edges on boundary of outer room.
It typical for contest. You achievements determined by your
first quick considerations.

WA6. Not so simple. More rightly to consider functional
equation for dist[i,j].This equation solved by method of
relaxation as a Laplas equation.

AC at last. The problem indeed very simple and very based
on the Floyd. But a man must have big contest experience
to catch all logical moments.

Edited by author 28.11.2008 20:58