Задача про дороги

[makskovalko]

Помогите решить задачку:

Файл входных данных Z5.DAT
Файл результатов Z5.SOL
Файлы решения задачи Z5.*

Текст задачи:
В Гондурасе n городов, пронумерованы от 1 до n, при этом некоторые города соединены двухсторонними дорогами. Все дороги имеют длину - некоторое целое число от 1 до 800. Известно, что из любого города можно доехать до любого другого по существующим дорогам. Так же для каждой пары городов известно кратчайшее расстояние между ними.
Правительство Гондураса планирует построить k новых дорог. Для каждой запланированной дороги известна ее длина и какие города она будет соединять. Чтобы контролировать правильность постройки новых городов, после открытия очередной дороги правительство Гондураса хочет проверять сумму кратчайших расстояний старых дорог и планам всех новых дорог, выясните, как будет меняться сумма кратчайших расстояний между всеми парами городов после постройки каждой дороги

Формат входных данных в файле Z5.DAT
В первой строке записано целое число n (2<=n<=300) - число городов в Гондурасе. Далее в n строках записано по n целых чисел - матрица кратчайших расстояний. j-ое число в i-ой строке - D[ij], кратчайшее расстояние между городами i и j. Гарантируется, что d[ii]=0,d[ji]=d[ij], и заданная матрица является матрицей кратчайших расстояний для некоторого набора двухсторонних дорог с многочисленной длиной от 1 до 1000, таким, что по этим дорогам можно доехать из любого города в любой другой.
В следующей строке записано целое число k (1<=k<=300) - число запланированных дорог. Каждая дорога описывается тремя целыми числами a[i], b[i], c[i] (1<=a[i],b[i]<=n,a[i]!=b[i],1<=c[i]<=1000) - a[i] и b[i] - пара городов, которые соединяет дорога, с[i] - длина дороги. Между парой городов может быть несколько дорог, но никакая дорога не соединяет город с самим собой

Формат выходных данных в файле Z5.SOL:
Выведите k целых чисел q[i] (1<=i<=k). q[i] должно равняться сумме кратчайших расстояний между всеми парами городов после постройки дорог с номерами от 1 до i. Дороги нумеруются начиная с 1 в том порядке, в котором они даны во входных данных. Каждая пара городов учитывается в сумме один раз, т.е. имеются виду неупорядоченные пары.

Пример входного и выходного файлов:
Z5.DAT:
2
0 12
12 0

Z5.SOL
10

[Poma][a]

Очевидно, что тест не полный..

И сколько можно копипастить свое задание, писать одну фразу :

Помогите решить задачку:

и ждать ответ.. Может хватит?
Вы хоть что-то сделали для решения задачи?

[Utkin]

Кратчайшие расстояния меряются в теории графов.
Есть:
а) задача коммивояжера
б) алгоритм Дейкстры
в) алгоритм Флойда
г) деревянный алгоритм
д) жадный алгоритм
и много других сходной тематики.
Просто выберите наиболее для Вас приемлимый.

ЗЫ. Учитывая что дороги двухсторонние задание вероятнее всего предполагает использовать алгоритмы связанные с эйлеровыми путями/циклами...