Как решить задачу по информатике 9 класс

Поехали. Два наиболее удаленных друг от друга города - это А и В

А-С-В=18
А-Д-В=19
А-Д-С-В=18

Кратчайшее расстояние 18

Это называется диаметр Графа.
Выбирай любую из этих вершин, и ищи минимальные расстояния от неё до других вершин.
Например, выбрана вершина D:
Сначала смотришь её соседей, то есть до A - минимальное расстояние 8, до B - 11, до C-10.
Далее смотришь соседей только что посещённых вершин, то есть соседи А, соседи В, соседи С, и если находишь более меньшие расстояния до D, то заменяешь предыдущие значения на новые. Этот алгоритм называется DFS, обход в глубину.
То есть ты по очереди рассматриваешь вершинки, до которых уже известно минимальное расстояние, и от них бежишь уже дальше по такой же схеме (смотришь соседей и меняешь расстояния, если они стали меньше)
В итоге получится, что минимальные расстояния от вершины D, до других вершин равно:
до А - 8
до B - 10
до С - 9
до Е - 6

Из них самое большое расстояние - до B, то есть B - одна из двух вершин, между которыми наибольшее расстояние в графе.

Осталось найти вторую вершину. Тут можно просто взять и выбрать вершину В, для которой мы будем делать DFS (искать минимальные расстояния до других вершин)

С помощью таких же действий, как и в прошлый раз, получаешь, что минимальные расстояния от B:
до А равно 18, до С равно 1, до D равно 10, до Е равно 16.
То есть диаметр графа - расстояние между вершинами А и В, то есть 17.

Задавай вопросы, если что-то не понятно, потому что я объяснял в общем виде.

Для мелких графов просто проще перебором, но если у тебя полный граф на 10 вершин, то там уже не переберёшь, так что советую разобраться в этом.

Скорее всего тебе просто было непонятно условие.

Там имелось ввиду, что нужно найти такую пару вершин, кратчайшее расстояние между которыми будет максимальным, то есть кратчайшее расстояние для этой пары не меньше каждого из минимальных расстояний между другими парами вершин.

Если что-то не понятно ( я допускаю это, так как запутаться легко ), то задавай вопросы в комментариях.