1
0

exchange.pas 1.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
  1. Program Ural1162_Currency_Exchange;
  2. Const
  3. Fin='';//'Input.in';
  4. Maxn=100;
  5. Type
  6. Link=^Node;
  7. Node=Record
  8. v:Integer; {顶点}
  9. rate,less:Double; {兑换比率和中转费用}
  10. Next:Link;
  11. End;
  12. Var
  13. Map:Array[1..Maxn]of Link; {用邻接表存图}
  14. Dist:Array[1..Maxn]of Double; {最短路估计值}
  15. n,s:Integer; {顶点总数和源点}
  16. v:Double; {开始时拥有的货币数}
  17. Procedure Init; {读入}
  18. Var i,j,k,m:Integer;
  19. p:Link;
  20. Begin
  21. Assign(Input,Fin);
  22. Reset(Input);
  23. Readln(n,m,s,v);
  24. New(p); p:=Nil;
  25. For i:=1 to n do Map[i]:=p;
  26. For k:=1 to m do
  27. Begin
  28. Read(i,j);
  29. New(p);
  30. Read(p^.rate,p^.less);
  31. p^.v:=j; p^.Next:=Map[i]; Map[i]:=p;
  32. New(p);
  33. Readln(p^.rate,p^.less);
  34. p^.v:=i; p^.Next:=Map[j]; Map[j]:=p;
  35. End;
  36. End;
  37. Procedure Main; {用Bellman-Ford求最长路}
  38. Var i:Integer;
  39. Tt:Double;
  40. Quit:Boolean;
  41. p:Link;
  42. Begin
  43. For i:=1 to n do Dist[i]:=0; Dist[s]:=v;
  44. Repeat
  45. Quit:=True;
  46. For i:=1 to n do
  47. If Dist[i]>1e-8 Then {当前顶点由源点可达}
  48. Begin
  49. p:=Map[i];
  50. {对每条边进行松弛操作}
  51. While p<>Nil do
  52. Begin
  53. Tt:=(Dist[i]-p^.less)*p^.rate; {计算转移后可得到的货币数}
  54. If Tt>Dist[p^.v]+1e-8 Then
  55. Begin
  56. Dist[p^.v]:=Tt;
  57. Quit:=False; {记录该次循环有顶点的最短路估计值更新了}
  58. End;
  59. p:=p^.Next;
  60. End;
  61. End;
  62. Until Quit Or (Dist[s]>v+1e-8); {没有顶点可更新或已经得到比初始多的货币则退出}
  63. If Dist[s]>v+1e-8 Then Writeln('YES')
  64. Else Writeln('NO');
  65. End;
  66. Begin
  67. Init;
  68. Main;
  69. End.