|
Все привет! Помогите юному программисту с решением одной задачи (на паскале). Как будет выглядеть алгоритм поиска пути в задаче?
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" (нет решения). Решения для разных наборов входных данных должны разделяться в выходном файле пустой строкой.
|
