例一 exchange.pas

历届IOI国家集训队队员图论的论文

Program Ural1162_Currency_Exchange;
Const
  Fin='';//'Input.in';
  Maxn=100;

Type
  Link=^Node;
  Node=Record
         v:Integer; {顶点}
         rate,less:Double; {兑换比率和中转费用}
         Next:Link;
       End;

Var
  Map:Array[1..Maxn]of Link; {用邻接表存图}
  Dist:Array[1..Maxn]of Double; {最短路估计值}
  n,s:Integer; {顶点总数和源点}
  v:Double; {开始时拥有的货币数}

Procedure Init; {读入}
  Var i,j,k,m:Integer;
      p:Link;
  Begin
    Assign(Input,Fin);
    Reset(Input);
    Readln(n,m,s,v);
    New(p); p:=Nil;
    For i:=1 to n do Map[i]:=p;
    For k:=1 to m do
    Begin
      Read(i,j);
      New(p);
      Read(p^.rate,p^.less);
      p^.v:=j; p^.Next:=Map[i]; Map[i]:=p;
      New(p);
      Readln(p^.rate,p^.less);
      p^.v:=i; p^.Next:=Map[j]; Map[j]:=p;
    End;
  End;

Procedure Main; {用Bellman-Ford求最长路}
  Var i:Integer;
      Tt:Double;
      Quit:Boolean;
      p:Link;
  Begin
    For i:=1 to n do Dist[i]:=0; Dist[s]:=v;
    Repeat
      Quit:=True;
      For i:=1 to n do
      If Dist[i]>1e-8 Then {当前顶点由源点可达}
      Begin
        p:=Map[i];

        {对每条边进行松弛操作}
        While p<>Nil do
        Begin
          Tt:=(Dist[i]-p^.less)*p^.rate; {计算转移后可得到的货币数}
          If Tt>Dist[p^.v]+1e-8 Then
          Begin
            Dist[p^.v]:=Tt;
            Quit:=False; {记录该次循环有顶点的最短路估计值更新了}
          End;
          p:=p^.Next;
        End;
      End;
    Until Quit Or (Dist[s]>v+1e-8); {没有顶点可更新或已经得到比初始多的货币则退出}
    If Dist[s]>v+1e-8 Then Writeln('YES')
                      Else Writeln('NO');
  End;

Begin
  Init;
  Main;
End.