Курсовая работа: Алгоритмы на графах. Кратчайшие расстояния на графах

for j:=1 to kG[i] do Color[i,j]:=FREE;

Time[i]:=maxlongint;

end;

Time[vA]:=0; kv:=1; Sled[1]:=vA; OptT:=Maxlongint;

DFS(vA);

writeln(OptT);

for i:=1 to OptKv do writeln(OptSled[i]);

close(input); close(output);

end.

4 Задача "Скрудж Мак-Дак"

(Автор - Котов В.М.)

Республиканская олимпиада по информатике 1995г

Скрудж Мак-Дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта функция довольно сложна.

Его механик Винт Р. сделал устройство, вычисляющее эту функцию в несколько этапов с использование промежуточной памяти и вспомогательных функций. Для вычисления каждой из функций требуется, чтобы в ячейках памяти уже находились вычисленные параметры (которые являются значениями вычисленных функций), необходимые для ее вычисления. Вычисление функции без параметров может производится в любое время. После вычисления функции ячейки могут быть использованы повторно (хотя бы для записи результата вычисленной функции). Структура вызова функций такова, что каждая функция вычисляется не более одного раза и любой параметр используется не более одного раза. Любой параметр есть имя функции. Так как Скрудж не хочет тратить лишних денег на микросхемы, он поставил задачу минимизировать память прибора. По заданной структуре вызовов функций необходимо определить минимальный возможный размер памяти прибора и указать последовательность вычисления функций.

Входной файл INPUT.TXT

Формат ввода:

1 строка> <общее количество функций N>

2 строка> <имя функции, которую необходимо вычислить>

3 строка> <имя функции> <кол-во параметров>[<список имен параметров>]

...N+2 строка> <имя функции> <кол-во параметров>[<список имен параметров>]

Выходной файл OUTPUT.TXT

Формат вывода:

Размер памяти (в ячейках)

имя 1-й вычисляемой функции

имя 2-й вычисляемой функции

....имя функции, которую необходимо вычислить

Примечание: имя функции есть натуральное число от 1 до N.

Пример.

В кратком изложении в данной задаче требуется сделать следующее: