Описание
Царевна стоит в центре болота и громко плачет. Злой Кощей привязал ее к столбу веревкой так, что веревка обмоталась вокруг царевны ровно I раз по часовой стрелке. Иванушка хочет освободить царевну и взять ее в жены

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

Будем считать, что поверхность болота ровная, а веревка достаточно длинная и не может ни за что зацепиться либо запутаться. Иванушка должен, держа в руках конец этой веревки, проскакать по кочкам так, чтобы размотать царевну и вернуться на начальную кочку. Так как царевна очень изнежена, то она ни в какой момент времени не должна быть обмотана веревкой более десяти раз (иначе веревка поранит царевну)

Задание
Требуется определить такой маршрут движения Иванушки, при котором за его ноги зацепится минимально возможное количество водорослей


Входные данные
Первая строка входного файла содержит три целых числа: N - количество кочек в болоте (3
N10), I - количество оборотов веревки (1I6) и S - номер кочки, на которой в начальный момент стоит Иванушка (1SN). Каждая из следующих N строк содержит вещественные координаты одной из кочек, записанные через пробел. Известно, что никакой отрезок, соединяющий две кочки, не проходит через центр болота, имеющий по соглашению координаты (0,0)

В следующих N строках записана матрица N
×N, составленная из вещественных чисел. Число в i-ой строке и j-ом столбце этой матрицы означает количество водорослей, цепляющихся за ноги Иванушки при прыжке с i-ой кочки на j

Выходные данные
В первую строку выходного файла выведите минимально возможное количество водорослей, которые зацепятся за ноги Иванушки, с точностью до двух знаков после десятичной точки. Во вторую строку запишите соответствующий маршрут Иванушки, заданный номерами кочек, по которым он должен проскакать. Номера кочек разделяются пробелом


Например:

PRINCESS.IN
3 1 1
-1 0
0 1
1 -2
0 1 1
1 0 1
1 1 0

PRINCESS.OUT
3.00
1 3 2 1




Идеи
Кратчайший путь в графе, элементарная геометрия

Комментарии
Текущее состояние Иванушки в процессе прыжков определяется номером кочки, на которой он находится, и количеством оборотов веревки вокруг царевны. При этом количество оборотов мы можем считать целым числом из диапазона [-10,10], поскольку его дробная часть однозначно восстанавливается по номеру кочки. Построим граф, вершины которого будут соответствовать возможным состояниям Иванушки, т.е. парам (номер кочки, число оборотов), а ребра - допустимым переходам между ними (т.е. прыжкам Иванушки с одной кочки на другую). Каждому ребру припишем вес, равный количеству зеленых водорослей, цепляющихся за ноги Иванушки при соответствующем прыжке. Теперь можно воспользоваться алгоритмом Дейкстры [Липский 88, п.3.3] для нахождения в полученном графе кратчайшего пути из начальной вершины в конечную





Решение

{$A+,B-,D+,E-,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}
 
program princess;
type
  real = extended;
  Point=Record
           X,Y:Real;
         End;
const NMax=10;
var K:Array[1..NMax] of Point;
    A:Array[1..NMax,1..NMax] of Real;
    N,S,R:Integer;
 
Procedure Init;
Var i,j:Integer;
Begin
  Read(N, R, S);
 
  For i:=1 to N do
    Read(K[i].X,K[i].Y);
 
  For i:=1 to N do
    For j:=1 to N do
      Read(A[i,j]);
End(*Init*);
 
Type Line=Record
            A,B,C:Real;
          End;
 
Var Jump:Array[1..NMax,1..NMax] of Integer;
    Lines:Array[1..NMax] of Line;
 
Procedure EqLine(Var L:Line;P:Point);
Begin
  L.A:=-P.Y;
  L.B:=P.X;
  L.C:=0;
End(*EqLine*);
 
Procedure InitLines;
Var i:Integer;
Begin
  For i:=1 to N do
    EqLine(Lines[i],K[i]);
End(*InitLines*);
 
Function Res(P:Point;L:Line):Real;
Begin
  Res:=L.A*P.X+L.B*P.Y+L.C;
End(*Res*);
 
Function Eq(A,B:Real):Boolean;
Const Delta=0.000001;
Begin
  Eq:=False;
  If Abs(A-B)then
    Eq:=True;
End(*Eq*);
 
Function Sign(A:Real):Integer;
Begin
  If Eq(A,0) then
    Sign:=0
  Else
    If A>0 then
      Sign:=1
    Else
      Sign:=-1;
End(*Sign*);
 
Function AlongCl(P1,P2:Point):Boolean;
Var T:Real;
Begin
  T:=P2.X*P1.Y-P1.X*P2.Y;
  AlongCl:=Not Eq(T,0) and (T>0);
End(*AlongCl*);
 
Function STr(P1,P2,P3:Point):Real;
Begin
  STr:=P1.X*(P3.Y-P2.Y)+P2.X*(P1.Y-P3.Y)+P3.X*(P2.Y-P1.Y);
End(*STr*);
 
Function SQuat(P1,P2,P3,P4:Point):Real;
Begin
  SQuat:=P1.X*(P4.Y-P2.Y)+P2.X*(P1.Y-P3.Y)+
         P3.X*(P2.Y-P4.Y)+P4.X*(P3.Y-P1.Y);
End(*SQuat*);
 
Procedure InitJump;
Var i,j:Integer;
    P:Point;
Begin
  InitLines;
 
  FillChar(Jump,SizeOf(Jump),0);
 
  P.X:=0;
  P.Y:=0;
 
  For i:=1 to N do
    For j:=1 to N do
      If i<>j then
        If (Sign(Res(K[S],Lines[i]))*Sign(Res(K[S],Lines[j]))>0) or
           (Sign(Res(K[i],Lines[j]))=0) then
          Jump[i,j]:=0
        Else
          If Sign(STr(P,K[i],K[j]))<>Sign(SQuat(P,K[i],K[S],K[j])) then
            Jump[i,j]:=0
          Else
            If Sign(STr(P,K[i],K[j]))=1 then
              If i=S then
                Jump[i,j]:=0
              Else
                Jump[i,j]:=1
            Else
              If j=S then
                Jump[i,j]:=0
              Else
                Jump[i,j]:=-1;
End(*InitJump*);
 
Const MaxRoute=10;
      MaxW=1E28;
 
Type O=Array[1..NMax,-MaxRoute..MaxRoute] of Real;
 
Var Pos,OldPos:O;
    Pred:Array[1..NMax,-MaxRoute..MaxRoute] of Integer;
 
Procedure InitPos;
Var i,j:Integer;
Begin
  For i:=1 to N do
    For j:=-MaxRoute to MaxRoute do
      Pos[i,j]:=MaxW;
 
  Pos[S,R]:=0;
End(*InitPos*);
 
Function Number(i,j,m:Integer):Real;
Begin
  If Abs(j-Jump[m,i])>MaxRoute then
    Number:=MaxW
  Else
    If (Pos[m,j-Jump[m,i]]+A[m,i]>MaxW) or
       Eq(Pos[m,j-Jump[m,i]]+A[m,i],MaxW) then
      Number:=MaxW
    Else
      Number:=Pos[m,j-Jump[m,i]]+A[m,i];
End(*Number*);
 
Procedure Solve;
Var i,j,m:Integer;
    W:Real;
    B:Boolean;
Begin
  InitJump;
  InitPos;
  FillChar(Pred,SizeOf(Pred),0);
 
  Repeat
    B:=True;
 
    For i:=1 to N do
      For j:=-MaxRoute to MaxRoute do
        If (i<>S) or (j<>R) then
          For m:=1 to N do
            If i<>m then
              Begin
                W:=Number(i,j,m);
                If Not Eq(W,Pos[i,j]) and (Wthen
                  Begin
                    Pos[i,j]:=W;
                    Pred[i,j]:=m;
                    B:=False;
                  End;
              End;
  Until B;
End(*Solve*);
 
Procedure Done;
Var Path:Array[1..2500] of Integer;
    i,m,i1,Cnt:Integer;
Begin
  Write(Pos[S,0]:0:2,' ');
 
  i:=S;
  m:=0;
  Cnt:=0;
  Repeat
    Inc(Cnt);
    Path[Cnt]:=i;
    i1:=Pred[i,m];
    Dec(m,Jump[i1,i]);
    i:=i1;
  Until (i=S) and (m=R);
  Inc(Cnt);
  Path[Cnt]:=S;
 
  For i:=Cnt downto 1 do
    Write(Path[i],' ');
  WriteLn;
End(*Done*);
 
Procedure Initialize;
Begin
  Assign(Input,'princess.in');
  ReSet(Input);
  Assign(Output,'princess.out');
  ReWrite(Output);
End(*Initialize*);
 
Procedure DoneAll;
Begin
  Close(Input);
  Close(Output);
End(*DoneAll*);
 
BEGIN
  Initialize;
 
  While Not SeekEof do
    Begin
      Init;
      Solve;
      Done;
    End;
 
  DoneAll;
END.

 


© Особенности национальных задач по информатике