TRAVEL

  • Путешествие
    TRAVEL

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

Задание
Вам предстоит составить программу TRAVEL, определяющую минимальную сумму, которую нужно иметь, чтобы проехать из одного княжества через все остальные, и указать маршрут движения, если:

  1. Ваше место начального положения - наилучшее из всех имеющихся, т.е. то, проезд из которого через все остальные дает наименьшую из возможных сумм пошлины.

  2. Данные о княжествах K(i), где i=1,2, ...,8 и величины пошлины 0<P(j)<=10000 между соответствующими соседними княжествами находятся в файле TRAVEL.DAT через пробел в одной строке для каждой пары

  3. Маршрут движения должен быть уникален, т.е. разрешается посещать каждое княжество только один раз

  4. Выходной файл TRAVEL.SOL должен содержать две строки. В первую из них заносится информация о маршруте движения, а во вторую - значение уплаченной пошлины


Например:

TRAVEL.DAT
1  2  47
...
где 1 2 - названия соседних княжеств, 47 - размер пошлины.

TRAVEL.SOL
4 - 3 - 7 - 1 - 2 - 5 - 6 - 8
89