Будем обозначать города буквами $A$, $B$, $C$, $D$,$\ldots$ Прежде всего заметим, что: 1) если какой-то путь $A—\ldots— B — \ldots — C — \ldots$ — кратчайший между городами $A$ и $C$, то часть его, например, от $A$ до $B$ — кратчайший путь между соответствующими городами; 2) кратчайший путь не проходит по одной дороге дважды.
Допустим теперь, что закрыли дорогу, соединяющую города $A$ и $B$; обозначим её через $AB$. Поделим все города на две группы: к первой группе отнесём город $A$ и те города, кратчайший путь из которых в город $A$ не проходил по дороге $AB$, а ко второй — все остальные. Нужно считать, что город $B$ окажется во второй группе — иначе во второй группе не будет вообще ни одного города; ведь если $AB$ — не кратчайший путь из $A$ и $B$, то ни один из кратчайших путей не может проходить по дороге $AB$, т. е. дорога $AB$ тогда — бесполезная.
Пусть $M$ и $N$ — города, кратчайший путь между которыми составляет теперь больше $500~\text{км}$. Значит, раньше кратчайший путь между $M$ и $N$ проходил по дороге $AB$. Но тогда кратчайший путь в город $A$ из одного из этих городов проходил по дороге $AB$, а из другого — нет (см. замечание в начале решения); следовательно, города $M$ и $N$ принадлежат разным группам. Рассуждая от противного, получаем, что любые два города, принадлежащие одной и той же группе, могут быть соединены путём длины меньше $500~\text{км}$.
Поскольку из города $A$ по-прежнему можно проехать в город $B$, то найдутся два города $C$ и $D$ такие, что $C$ принадлежит первой группе, а $D$ — второй, и город $C$ соединён дорогой с $D$. Теперь понятно, как из любого города $M$ первой группы попасть в любой город $N$ второй группы, проехав меньше $1500~\text{км}$: нужно из $M$ поехать вначале в город $C$ (этот путь меньше $500~\text{км}$, так как $M$ и $C$ принадлежат одной и той же группе), затем — из $C$ в $D$ (длина дороги $CD$ меньше $500~\text{км}$ по условию), и, наконец, из города $D$ — в город $N$ (города $D$ и $N$ — из одной группы, поэтому путь из $D$ в $N$ снова меньше $500~\text{км}$) — см. рисунок 1.
Рисунок 1
Оценку $1500~\text{км}$ нельзя улучшить. Действительно, если четыре города $A$, $B$, $C$ и $D$ расположены так, как показано на рисунке 2 ($ABCD$ — трапеция такая, что при продолжении её боковых сторон получается равносторонний треугольник), то, закрыв дорогу $AB$, получим, что длина кратчайшего пути между $A$ и $B$ равна ($500+2a)~\text{км}$, где $a$ можно сделать сколь угодно близким к $500$.
Рисунок 2
