Задача 'Канадские авиалинии'

[Дмитрий Келлерман]

Все привет! Помогите юному программисту с решением одной задачи (на паскале). Как будет выглядеть алгоритм поиска пути в задаче?
p.s. эта задача из IOI 93. спасибо заранее!!!!

Задача 'Канадские авиалинии'

Вы победили в соревновании, организованном Канадскими авиалиниями. Приз - бесплатное путешествие по Канаде. Путешествие начинается с самого западного города, в который летают самолеты, проходит с запада на восток, пока не достигнет самого восточного города, в который летают самолеты. Затем путешествие продолжается обратно с востока на запад, пока не достигнет начального города. Ни один из городов нельзя посещать более одного раза за исключением начального города, который надо посетить ровно дважды (в начале и в конце пу- тешествия). Вам также нельзя пользоваться авиалиниями других компаний или другими способами передвижения. Задача состоит в следующем: дан список городов и список прямых рейсов между парами городов; найти маршрут, включающий максимальное количество городов и удовлетворяющий вышеназванными условиям. Несколько наборов входных данных помещены в ASCII-файл C:\IOI\ITIN.DAT. Каждый набор содержит:
в первой строке - количество городов N, в которые летают самолеты, и количество прямых рейсов V. N - положительное целое число, меньшее или равное 100. V - положительное целое число;
в каждой из следующих N строк - название города, в который летают самолеты. Названия упорядочены с запада на восток, то есть i-ый по порядку город находится восточнее j-го тогда и только тогда, когда i> j (не существует городов на одном меридиане). Название каждого города - строка, состоящая из не более, чем 15 цифр и/или латинских букв, например: AGR34 или BELA
в каждой из следующих V строк - названия двух городов из списка городов, разделенные пробелом. Если пара ГОРОД1 ГОРОД2 содержится в строке, это означает, что есть прямой рейс из ГОРОД1 в ГОРОД2, а также прямой рейс из ГОРОД2 в ГОРОД1.

Различные наборы входных данных разделены пустой строкой. После последнего набора данных пустой строки не будет. Пример файла входных данных C:\IOI\ITIN.DAT:

Входные данные корректны, и их проверка не требуется. Решения, полученные для каждого набора входных данных, должны быть последовательно записаны в выходной ASCII-файл C:\IOI\ITIN.SOL следующим образом:
в первой строке - общее количество городов из входного файла;
в следующей строке - число M, равное количеству различных городов, посещаемых на маршруте;
в следующих M+1 строках - названия городов по одному в строке в порядке их посещения.

Обратите внимание, что исходный город должен быть также выведен последним. Если для набора входных данных не существует решения, то для этого набора в выходном файле C:\IOI\ITIN.SOL должны быть только две записи: общее количество городов и сообщение "NO SOLUTION" (нет решения). Решения для разных наборов входных данных должны разделяться в выходном файле пустой строкой.

[Maxim Vlasov]

Кроме рекурсивного обхода я навскидку не вижу. Если двигаться только в одном направлении, то можно было бы оптимизировать граф, но с "туда-обратно" нет идей как оптимизировать - оптимальный вариант для "туда" может дать неоптимальное общее решение.

Рекурсивно "в лоб" будет не очень эффективно. Но суть проста - выбираем первый возможный перелет из данного города и решаем задачу для заново, считая отправной точкой второй город.

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