Курсовая работа: Алгоритмы на графах. Кратчайшие расстояния на графах
end;
end;
begin
assign(input,'path.in'); reset(input);
assign(output,'path.out'); rewrite(output);
read(N,M);
for i:=1 to M do
begin
read(x,y); inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;
end;
read(A,B,C);
LabC:=0;
DFS(A);
writeln(-1);
close(input); close(output);
end.
3 Задача "Перекрестки"
(Автор - Котов В.М.)
Республиканская олимпиада по информатике 1998г
Даны декартовы координаты N перекрестков города, которые пронумерованы от 1 до N. На каждом перекрестке имеется светофор. Некоторые из перекрестков соединены дорогами с двухсторонним (правосторонним) движением, которые пересекаются только на перекрестках. Для каждой дороги известно время, которое требуется для проезда по ней от одного перекрестка до другого.
Необходимо проехать от перекрестка с номером А до перекрестка с номером В за минимальное время.
Время проезда зависит от набора проезжаемых дорог и от времени ожидания на перекрестках. Так, если вы подъехали от перекрестка X к перекрестку C по дороге Х->C и хотите ехать дальше по дороге C->У, то время ожидания на перекрестке C эависит от того, поворачиваете ли вы налево или нет. Если вы поворачиваете налево, то время ожидания равно D*К, где D равно количеству дорог, пересекающихся на перекрестке C, а К - некоторая константа. Если вы не поворачиваете налево, то время ожидания равно нулю.
Написать программу, которая определяет самый быстрый маршрут.
Спецификация входных данных.
Входные данные находятся в текстовом файле с именем PER.IN и имеют следующую структуру:
- в первой строке находится число N (натуральное, <=1000);
- во второй строке - количество дорог M (натуральное, <=1000);
- в третьей строке - константа K (натуральное число, <=1000);
- в каждой из N следующих стpок находится паpа чисел х и у, разделенных пробелом, где x, y - кооpдинаты перекрестка (целые числа, не пpевышающие по модулю 1000);
- в каждой из M следующих строк находится 3 числа p, r, t, разделенные пробелом, где p и r - номера перекрестков, которые соединяет дорога, а t (натуральное, <=1000) - время проезда по ней;