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

Имеется N городов, которые пронумерованы от 1 до N (где N - натуральное, 1<N<=100). Некоторые из них соединены двухсторонними дорогами, которые пересекаются только в городах. Имеется два типа дорог - шоссейные и железные. Для каждой дороги известна базовая стоимость проезда по ней.

Необходимо проехать из города А в город В, уплатив минимальную сумму за проезд. Стоимость проезда зависит от набора проезжаемых дорог и от способа проезда. Так, если вы подъехали к городу С по шоссейной (железной) дороге X->C и хотите ехать дальше по дороге C->Y того же типа, то вы должны уплатить только базовую стоимость проезда по дороге C->Y. Если тип дороги C->Y отличен от типа дороги Х->C, то вы должны уплатить базовую стоимость проезда по дороге C->Y плюс 10% от базовой стоимости проезда по этой дороге (страховой взнос). При выезде из города А страховой взнос платится всегда. Написать программу, которая находит самый дешевый маршрут проезда в виде последовательности городов и вычисляет стоимость проезда по этому маршруту.

Спецификация входных данных

Входные данные находятся в текстовом файле с именем TOUR.IN и имеют следующий формат:

- в первой строке находятся число N

- во второй строке - число M (количество дорог, натуральное M<=1000);

- в каждой из следующих M строк находятся 4 числа x, y, t, p, разделенные пробелом, где x и y - номера городов, которые соединяет дорога, t - тип дороги (0 - шоссейная, 1 - железная), p - базовая стоимость проезда по ней (p - вещественное, 0<p<=1000).

- в последней строке задается номера начального и конечного городов A и B.

Спецификация выходных данных

Выходные данные должны быть записаны в текстовый файл с именем TOUR.OUT и иметь следующий формат:

- в первой строке находится число S - стоимость проезда по самому дешевому маршруту, с точностью 2 знака после запятой;

- в каждой из последующих строк, кроме последней, находится два числа - номер очередного города в маршруте (начиная с города А) и тип дороги, по которой он выезжает из этого города (0 или 1), разделенные пробелом.

- в последней строке находится единственное число - номер города B.

Пример входного файла Пример выходного файла

TOUR.IN TOUR.OUT

3 22.0

2 1 0

1 2 0 10.00 2 1

2 3 1 10.00 3

1 3

Метод Дейкстра непосредственно (города - вершины) не может быть применен, поскольку оптимальный маршрут может потребовать заезда в один и тот же город два раза с целью меньше платить за страховой сбор на выезд из этого города.

Вводим 2*N вершин (где N - число городов). Для каждого города - две вершины. Первая, если мы въехали в город по дороге типа 0, вторая - если въехали в город по дороге типа 1.

Теперь можно применять непосредственно метод Дейкстра для вычисления кратчайших расстояний от заданного города A до всех введенных вершин.

Для конечного города B мы выбираем лучший из вариантов - заехать в B по дороге типа 0 или по дороге типа 1.

Метод Дейкстра позволяет сохранять предшественников вершин на оптимальном маршруте, что и используется для вывода полного ответа в заданном формате.

Рассмотрим решение задачи более подробно, основываясь на тексте программы - решения:

Ввод исходных данных осуществляется следующим образом:

read(N); {N - число городов}

read(M); {M - число дорог}

for x:=1 to N do {Устанавливаем}

for y:=1 to N do {между всеми городами}

for t:=0 to 1 do p[x,y,t]:=MAXR; {максимальную стоимость}

for i:=1 to M do {x - номер города "откуда"}

begin {y - номер города "куда"}

readln (x,y,t,p[x,y,t]); {t - тип дороги}

p[y,x,t]:=p[x,y,t]; {P[x,y,t] - стоимость}

end; {проезда от x к y по дороге типа t}

read(A,B); {Начальный и конечный пункты маршрута}

Подготовка к выполнению алгорима Дейкстра:

for i:=1 to N do {При выезде из города}

for t:=0 to 1 do {страховой взнос}

p[a,i,t]:=1.1*p[a,i,t]; {платится всегда}

for i:=1 to N do {Для всех городов}

begin {кратчайшие стоимости до первого}

D[i,0]:=P[a,i,0]; {по шоссейной дороге}

D[i,1]:=P[a,i,1]; {по железной дороге}

end;

for i:=1 to N do {Для всех городов}

begin

Labl[i,0]:=FREE; {Свободны}

Labl[i,1]:=FREE; {по обоим типам дорог}

pred[i,0]:=A; {Предыдущий город равен A}

pred[i,1]:=A; {для обоих типов дорог}

end;

Labl[A,0]:=DONE; {Начальный город обработан}

abl[A,1]:=DONE; {для обоих типов дорог}

pred[A,0]:=0; {Предыдущий у начального-0}

pred[A,1]:=0; {для обоих типов дорог}

Основная часть алгоритма Дейкстра представляет собой цикл по количеству вершин оставшихся необработанными

for i:=1 to 2*N-2 do

begin

Поиск ближайшей к первой вершине из необработанных

Пересчет наименьших стоимостей через ближайшую вершину до вершин, смежных с ближайшей end;

Первый этап - "Поиск ближайшей к первой вершине из необработанных"

MinD:=MaxR; {MinD - максимум}

for J:=1 to N do {Для всех городов}

for t:=0 to 1 do {Для дорог обоих типов}

if (Labl[j,t]=FREE) {Если въезд в город j по дороге типа t}

and {еще не обрабатывался и}

(minD>d[j,t]) {стоимость от города A до города j}

then {по дороге типа t меньше чем MinD, то}

begin

Bliz:=j; {Ближайшаяя - j}

bt:=t; {ее тип - bt}

MinD:=d[j,t] {минимальную стоимость в MinD}

end;

Labl[Bliz,bt]:=DONE; {Пометить как обработанную вершину}

{с минимальной стоимостью от города A}

{из еще необработанных вершин}

Второй этап - "Пересчет наименьших стоимостей через ближайшую вершину до вершин, смежных с ближайшей"

for j:=1 to N do {Для всех городов}

for t1:=0 to 1 do {Для дорог обоих типов}

if (Labl[j,t1]=FREE) {Если дорога до города j типа t необработана}

and (d[j,t1] {и стоимость до нее от вершины A}

> {больше чем}

d[Bliz,bt] + C(t1,bt)*P[Bliz,j,t1]) {стоимость через ближайшую}

then {то}

begin

d[j,t1]:=d[Bliz,bt]+C(t1,bt)*P[Bliz,j,t1]; {заменяем стоимость}

Pred[j,t1]:=Bliz; Typp[j,t1]:=bt; {запоминаем}

end; {предыдущие город и тип дороги}

При вычислении стоимости проезда через ближайшую вершину учитывается страховой сбор при переходе с дороги одного типа на дорогу другого типа с помощью функции C(t1,t2):

function C(t1,t2:byte):real;

begin

if t1=t2 then C:=1.0 else C:=1.1

end;

Вывод результатов осуществляется так:

G:=B; is:=0; {Текущий город - конечный город}

if d[B,0]<d[B,1] {Тип въезда -}

then t:=0 else t:=1; {лучший из двух возможных}

stt[1]:=t; {Текущий тип - выбранный лучший}

while (G<>0) do {Пока текущий город не равен 0}

begin

inc(is); {Инкрементируем количество городов}

stg[is]:=pred[G,t]; {сохраняем текущий город в путь}

stt[is+1]:=typp[G,t]; {и его тип}

NG:=pred[G,t]; {Переустанавливаем текущие город}

NT:=typp[G,T]; {и тип на предыдущие город}

G:=NG; t:=NT; {и тип}

end;

writeln(min(d[B,0],d[B,1]):0:2); {выводим минимальную стоимость}

for i:=is-1 downto 1 do writeln(stg[i],' ',stt[i]); {и путь}

writeln(B); {добавляем в путь последний город}

Далее приводится полный текст решения задачи.

{$R+,E+,N+}

program by98d1m2;

const

FREE = 0;

DONE = 1;

MAXR = 1e4;

var

p : array [1..80,1..80,0..1] of single;

D : array [1..80,0..1] of single;

pred : array [1..80,0..1] of 0..100;

typp,Labl : array [1..80,0..1] of 0..1;

stg : array [1..100] of 0..100;

stt : array [1..100] of 0..1;

M : 0..1000;

N,x,y,A,B,i,k,j,G,NG : 0..100;

t,t1,t2,bt,NT : 0..1;

is,Bliz : 0..100;

Mind : single;

Mint,MT : byte;

function C(t1,t2:byte):real;

begin

if t1=t2 then C:=1.0 else C:=1.1

end;

function min(x,y:single):single;

begin

if x<=y then min:=x else min:=y

end;

begin

assign(input,'tour.in'); reset(input);

assign(output,'tour.out'); rewrite(output);

read(N);

read(M);

for x:=1 to N do

for y:=1 to N do

for t:=0 to 1 do p[x,y,t]:=MAXR;

for i:=1 to M do

begin

readln (x,y,t,p[x,y,t]); p[y,x,t]:=p[x,y,t];

end;

read(A,B);

for i:=1 to N do

for t:=0 to 1 do p[a,i,t]:=1.1*p[a,i,t];

for i:=1 to N do

begin D[i,0]:=P[a,i,0]; D[i,1] :=P[a,i,1]; end;

for i:=1 to N do

begin

Labl[i,0]:=FREE; Labl[i,1]:=FREE;

pred[i,0]:=A; pred[i,1]:=A;

end;

Labl[A,0]:=DONE; Labl[A,1]:=DONE; pred[A,0]:=0; Pred[A,1]:=0;

for i:=1 to 2*N-2 do

begin

MinD:=MaxR;

for J:=1 to N do

for t:=0 to 1 do

if (Labl[j,t]=FREE) and (minD>d[j,t])

then begin

Bliz:=j; bt:=t; MinD:=d[j,t]

end;

Labl[Bliz,bt]:=DONE;

for j:=1 to N do

for t1:=0 to 1 do

if (Labl[j,t1]=FREE) and

(d[j,t1]>d[Bliz,bt] + C(t1,bt)*P[Bliz,j,t1])

then begin

d[j,t1]:=d[Bliz,bt]+C(t1,bt)*P[Bliz,j,t1];

Pred[j,t1]:=Bliz; Typp[j,t1]:=bt;

end;

end;

G:=B; is:=0;

if d[B,0]<d[B,1] then t:=0 else t:=1;

stt[1]:=t;

while (G<>0) do

begin

inc(is);

stg[is]:=pred[G,t]; stt[is+1]:=typp[G,t];

NG:=pred[G,t]; NT:=typp[G,T];

G:=NG; t:=NT;

end;

writeln (min(d[B,0],d[B,1]):0:2);

for i:=is-1 downto 1 do writeln(stg[i],' ',stt[i]);

writeln(B);

close(input); close(output);

end.

3. Поиск в глубину

(1)--(3) (5)

I \ / I I

I / \ I I

(2)--(4) (6)

При компьютерной обработке граф может задаваться списком ребер (дуг) для каждой вершины. Например, для графа, приведенного на примере, этот список выглядит так

1: 2,3,4 (первая вершина соединена со второй, третьей и четвертой)

2: 1,3,4

3: 2,3,4

4: 1,2,3

5: 6

6: 5

Для хранения этой информации в памяти компьютера можно воспользоваться двумерным массивом G[1..N,1..M], где N - число вершин в графе, M - максимально возможное число ребер (дуг) у одной вершины графа. Для удобства обработки этой информации можно также иметь одномерный массив kG[1..N] - количества ребер (дуг) вершин графа.

Тогда для обработки списка связей текущей вершины U можно написать

for i:=1 to kG[U]

begin

V:=G[U,i];

end;

Тем самым, мы получаем обработку дуги, связывающей вершины U и V для всех вершин, непосредственно связанных с U.

Для обработки ВСЕХ связей всех вершин можно использовать поиск в глубину (DFS - Depth-First Search):

for U:=1 to N do Color[U]:=WHITE;

for U:=1 to N do

if color[U]=WHITE then DFS(U);

Procedure DFS(U:longint);

var

j : longint;

begin

color[U]:=GRAY;

for j:=1 to kG[U] do DFS(G[U,j]);

end;

Здесь

Color[U] = цвет вершины

WHITE (константа=1) - белый,

если мы еще не посещали эту вершину

GRAY (константа=2) - серый,

если мы посещали данную вершину

DFS(U) - рекурсивная процедура, которая вызывает себя

для всех вершин, потомков данной вершины.

То есть, для обеспечения поиска в глубину на заданном графе G[1..N,1..M] с количествами дуг из вершин G[1..N], вначале мы устанавливаем всем вершинам цвет WHITE, а затем для всех вершин, которые еще не посещались (Color[G[U,j]]=WHITE) вызываем рекурсивную процедуру DFS.

Таким способом формируются все возможные маршруты в графе.При этом нет ограничений на количество раз использования дуг и заходов в вершины.

Если же по условиям задачи потребуется посещать каждую вершину не более одного раза, чтобы формировать маршруты из несовпадающих вершин, то это может быть обеспечено в процедуре DFS условным вызовом:

Procedure DFS(U:longint);

var

j : longint;

begin

color[U]:=GRAY;

for j:=1 to kG[U] do

if color[G[U,j]]=WHITE then DFS(G[U,j]);

end;

Если по условиям задачи требуется каждую дугу использовать не более одного раза, то можно ввести расцветку дуг:

Color[1..N,1..M] - со значениями FREE или DONE

где, как и ранее

N - число вершин в графе,

M - максимально возможное число ребер (дуг) у одной вершины графа.

А процедура DFS формирования маршрутов так, что бы каждая дуга использовалась в маршруте не более одного раза, будет выглядеть следующим образом:

procedure DFS(v:byte);

var j : byte;

begin

for j:=1 to kG[v] do

if (color[v,j]=FREE)

then

begin

color[v,j]:=DONE;

DFS(G[v,j]);

color[v,j]:=FREE;

end;

end;

Здесь вводятся пометки на дуги Color[v,j] = FREE, если дуга еще не обработана, и DONE, если она включена в текущий путь.

Если в задаче требуется вывести найденный путь, то для его хранения заводится специальный массив SLED [1..Q], где Q - максимальное количество ребер в пути и вершины текущего пути заносятся в этот массив и удаляются из него в процессе обхода графа:

procedure DFS(v:byte);

var j : byte;

begin

for j:=1 to kG[v] do

begin

inc(ks); sled[ks]:=G[v,j];

DFS(G[v,j]);

dec(ks);

...

end;

end;

Приведенная теоретическая информация иллюстрируется далее примерами решения конкретных задач.

3.1 Задача "Дороги"

3.2 Задача "Перекрестки" (Автор - Котов В.М.)

Республиканская олимпиада по информатике 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) - время проезда по ней;

- в последней строке находятся номера начального А и конечного В перекрестков.

Спецификация выходных данных.

Выходные данные должны быть записаны в текстовый файл с именем PER.OUT и иметь следующий формат:

- в первой строке находится натуральное число T - время проезда по самому быстрому маршруту;

- в каждой из следующих строк находится одно число - номер очередного перекрестка в маршруте (начиная с перекрестка с номером А и кончая В).

Кратко идея решения может быть изложена следующим образом.

Алгоритм Дейкстры напрямую не применим, поскольку:

а) оптимальное решение в следующей вершине не является суммой оптимального решения для предыдущей вершины и веса текущего ребра

б) вес текущего ребра - непостоянная величина, зависящая от того, каким поворотом мы вышли из вершины.

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

Можно еще ускорить решение, если обеспечивать перебор, начиная с правых поворотов (отсечения работали бы более эффективно).

Замечание:

В тексте задачи явно не указано, но авторы оригинальных тестов к задаче полагали, что поворот на 180 градусов - это левый поворот (как в армии: поворот на 180 градусов - "через левое плечо").

Рассмотрим решение более подробно:

Ввод исходных данных осуществляется следующим образом:

read(N,M,K);

for i:=1 to N do readln(x[i],y[i]);

for i:=1 to N do begin kG[i]:=0; D[i]:=0; end;

for i:=1 to M do

begin

readln(p,r,t); inc(kG[p]); inc(kG[r]);

G[p,kG[p],1]:=r; G[p,kG[p],2]:=t; inc(D[p]);

G[r,kG[r],1]:=p; G[r,kG[r],2]:=t; Inc(D[r]);

end;

readln(vA,vB);

Здесь

kG[i] - количество дуг из вершины i

G[i,j,1] - вершина, с которой соединена вершина i дугой

с номером j в списке всех дуг из вершины i.

$G[i,j,2] - время проезда от вершины i до вершины, с которой она соединена дугой j в списке всех дуг из вершины i.

D[i] - количество дорог, пересекающихся на перекрестке i (то есть суммарное количество дуг, исходящих из вершины i и входящик в нее)

vA и vB указывают, откуда и куда нужно добираться.

Поскольку по условиям задачи дороги двусторонние, то, для каждой введенной дороги, мы добавляем в граф две дуги.

Основной алгоритм выглядит следующим образом:

for i:=1 to N do

begin

for j:=1 to kG[i] do Color[i,j]:=WHITE; {все дуги свободны}

Time[i]:=maxlongint; {время маршрута до I - максимально}

end;

OptT:=Maxlongint; {Оптимальное время - максимально}

Sled[1]:=vA; {Заносим в маршрут вершину vA}

kv:=1; {Количество вершин в маршруте = 1}

Time[vA]:=0; {Оптимальное время до вершины vA =0}

DFS(vA); {Поиск в глубину от вершины vA}

... вывод ответа ...

Рекурсивная процедура DFS(i) обеспечивает выполнение cледующей работы:

Procedure DFS(i)

...

begin

for j:=1 to kG[i] do

if G[i,j,1]<>vB

then

begin

if color[i,j]=FREE

then

begin

... продолжение пути с вызовом DFS

end

end

else

begin

... сравнение пути с текущим оптимальным

end;

end;

Если текущая вершина - конечная (vB), то делаем " ... сравнение пути с оптимальным"

Иначе проверяем, если текущая дуга еще не использовась (color[i,j]=FREE) то делаем "... продолжение пути с вызовом DFS".

При этом, перед входом в DFS помечаем дугу как использованную (color[i,j]:=DONE), а после выхода - как вновь свободную (color[i,j]:=FREE);

"... продолжение пути с вызовом DFS" включает в себя следующие операторы:

inc(kv); sled[kv]:=G[i,j,1]; {помещаем в путь новую вершину}

NewTime:=Time[i]+G[i,j,2]+CountTime; {вычисляем новое время}

if NewTime<OptT {если новое время меньше оптимального}

then {то продолжаем,иначе - отсекаем}

begin

color[i,j]:=DONE; {Помечаем - ребро использовано}

RetTime:=Time[G[i,j,1]]; {Сохраняем старое время}

Time[G[i,j,1]]:=NewTime; {Устанавливаем новое время}

DFS(G[i,j,1]); {Вызываем поиск от G[i,j,1]}

Time[G[i,j,1]]:=RetTime; {Восстанавливаем старое время}

color[i,j]:=FREE; {Помечаем - ребро свободно}

end;

Sled[kv]:=0; dec(kv); {Удаляем вершину из пути}

Для вычисления нового времени здесь используется функция CounTime с параметром kv - номер последней вершины в стеке.Эта функция делает следующее: Восстанавливает номера вершин, прохода через перекресток "из i1 через i2 в i3":

if kv=2 then begin CountTime:=0; exit; end;

i1 := sled[kv-2];

i2 := sled[kv-1];

i3 := sled[kv];

if i3=i1 then begin CountTime:=K*D[i2]; exit; end;

Попутно, выясняется

а) если вершин в пути всего 2, то есть не было никакого поворота - это шаг из начальной вершины и CountTime=0.

б) если i1=i3 то это поворот на 180 градусов и авторы задачи считают, что это тоже левый поворот, CountTime=K*D[i2]; где, K - коэффициент который вводится, i2 - перекресток, D[i2] - количество дорог, входящих в этот перекресток.

Затем из массивов координат перекрестков выбираются координаты текущих перекрестков: (x1,y1) (откуда); (x2,y2) (через какой); (x3,y3) (куда).

x1 := x[i1]; x2:=x[i2]; x3:=x[i3];

y1 := y[i1]; y2:=y[i2]; y3:=y[i3];

Вычисляется уравнение прямой по точкам (x1,y1) и (x2,y2)

A := y2-y1;

B := x1-x2;

C := y1*(x2-x1)-x1*(y2-y1);

Подстановкой координат (x3,y3) в уравнение прямой Ax+By+C=0, построенной по первым двум точкам (x1,y1) и (x2,y2) и с учетом крайних случаев, когда прямая параллельна осям координат, вычисляем, был ли поворот левым или правым и соответственно устанавливаем значение функции CountTime.

Left := (((x2>x1) and ((A*x3+B*y3+C)<0))) or

(((x2<x1) and ((A*x3+B*y3+C)<0))) or

(((y2=y1) and (x1>x2) and (y3<y1))) or

(((y2=y1) and (x1<x2) and (y3>y1))) or

(((x2=x1) and (y1>y2) and (x3>x1))) or

(((x2=x1) and (y1<y2) and (x3<x1))) ;

if Left

then CountTime:=K*D[i2]

else CountTime:=0;

"Сравнение пути с оптимальным" выполняется следующим образом:

inc(kv); sled[kv]:=G[i,j,1];

T := Time[i]+G[i,j,2] + CountTime;

if T < OptT

then begin

OptT:=T;

OptKv:=kv; OptSled:=Sled;

end;

Sled[kv]:=0; dec(kv);

Таким образом, оптимальное время хранится в переменной OptT а оптимальный путь храниться в массиве OptSled с количеством элементов OptKv. И потому, вывод результатов выглядит так:

writeln(OptT);

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

Полный текст программы приводится ниже

program by98d2s2;

Const

FREE = 1;

DONE = 2;

Type

int1000 = 0..1000;

int3 = 1..3;

var

G : array[1..1000,1..10,1..2] of int1000;

Time,D : array[1..1000] of longint;

x,y,kG,Sled,OptSled,pred : array[1..1000] of int1000;

Color : array[1..100,1..10] of int3;

N,M,K,i,p,r,t,vA,vB,v,kv,OptKv,j : int1000;

OptT : longint;

function CountTime(i:int1000):longint;

var

Left : boolean;

i1,i2,i3 : int1000;

x1,x2,x3,y1,y2,y3,A,B,C : longint;

begin

if kv=2 then begin CountTime:=0; exit; end;

i1 := sled[kv-2];

i2 := sled[kv-1];

i3 := sled[kv];

if i3=i1 then begin CountTime:=K*D[i2]; exit; end;

x1 := x[i1]; x2:=x[i2]; x3:=x[i3];

y1 := y[i1]; y2:=y[i2]; y3:=y[i3];

A := y2-y1;

B := x1-x2;

C := y1*(x2-x1)-x1*(y2-y1);

Left := (((x2>x1) and ((A*x3+B*y3+C)<0))) or

(((x2<x1) and ((A*x3+B*y3+C)<0))) or

(((y2=y1) and (x1>x2) and (y3<y1))) or

(((y2=y1) and (x1<x2) and (y3>y1))) or

(((x2=x1) and (y1>y2) and (x3>x1))) or

(((x2=x1) and (y1<y2) and (x3<x1))) ;

if Left

then CountTime:=K*D[i2]

else CountTime:=0;

end;

Procedure DFS(i:int1000);

var

j : byte;

T : longint;

RetSled,RetPred,RetTime :longint;

begin

for j:=1 to kG[i] do

if G[i,j,1]<>vB

then

begin

if color[i,j]=FREE

then

begin

inc(kv); sled[kv]:=G[i,j,1];

NewTime:=Time[i]+G[i,j,2]+CountTime;

if NewTime<OptT

then

begin

color[i,j]:=DONE;

RetTime:=Time[G[i,j,1]];

Time[G[i,j,1]]:=NewTime;

DFS(G[i,j,1]);

Time[G[i,j,1]]:=RetTime;

color[i,j]:=FREE;

end;

Sled[kv]:=0; dec(kv);

end

end

else

begin

inc(kv); sled[kv]:=G[i,j,1];

T := Time[i]+G[i,j,2] + CountTime;

if T < OptT

then begin

OptT:=T;

OptKv:=kv; OptSled:=Sled;

end;

Sled[kv]:=0; dec(kv);

end;

end;

begin

assign(input,'PER.in'); reset(input);

assign(output,'PER.out'); rewrite(output);

read(N,M,K);

for i:=1 to N do readln(x[i],y[i]);

for i:=1 to N do begin kG[i]:=0; D[i]:=0; end;

for i:=1 to M do

begin

readln(p,r,t); inc(kG[p]); inc(kG[r]);

G[p,kG[p],1]:=r; G[p,kG[p],2]:=t; inc(D[p]);

G[r,kG[r],1]:=p; G[r,kG[r],2]:=t; Inc(D[r]);

end;

readln(vA,vB);

for i:=1 to N do

begin

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.

3.3 Задача "Скрудж Мак-Дак" (Автор - Котов В.М.)