PRO_1_2.pas 2.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293
  1. Program Pro_1_2; {用“动态规划”的方法解决例1}
  2. Const
  3. Max =300; {最多的城市数}
  4. Inputfile ='Input.Txt'; {输入文件名}
  5. Outputfile ='Output.Txt'; {输出文件名}
  6. Big =1000000; {最大整数}
  7. Type
  8. Maps =Array[1..Max] Of Integer; {地图类型说明}
  9. Var
  10. Se :Set Of Byte; {未访问过的城市集合}
  11. Map :Array[1..Max] Of ^maps; {地图变量}
  12. Dis :Array[1..Max] Of Longint; {某城市到终点城市的最短距离}
  13. Fr :Array[1..Max] Of Byte; {动态规划的标识数组}
  14. Bo :Array[1..Max] Of Boolean; {访问过城市标识}
  15. N,M :Integer; {输入数据}
  16. F :Text; {文件变量}
  17. Procedure Init; {初始化过程}
  18. Var
  19. I,J,K,W :Integer;
  20. Begin
  21. Assign(F,Inputfile); {读入数据}
  22. Reset(F);
  23. Readln(F,N,M);
  24. For I:=1 To N Do
  25. Begin
  26. New(Map[I]);
  27. Fillchar(Map[I]^,Sizeof(Map[I]^),0);
  28. End;
  29. For I:=1 To M Do
  30. Begin
  31. Readln(F,J,K,W);
  32. Map[J]^[K]:=W;
  33. End;
  34. Close(F);
  35. End;
  36. Procedure Main; {动态规划递推过程}
  37. Var
  38. I,J,Who :Integer;
  39. Min :Longint; {当前最小值}
  40. Begin
  41. Dis[N]:=0; {初始化动态规划数组}
  42. Who:=N;
  43. Fillchar(Fr,Sizeof(Fr),0);
  44. Fillchar(Bo,Sizeof(Bo),True);
  45. Bo[N]:=False;
  46. While Who<>1 Do
  47. Begin
  48. For I:=1 To N Do {利用“状态转移方程”递推结果}
  49. If Map[I]^[Who]>0 Then
  50. If (Fr[I]=0) Or (Dis[I]>Dis[Who]+Map[I]^[Who]) Then
  51. Begin
  52. Dis[I]:=Dis[Who]+Map[I]^[Who];
  53. Fr[I]:=Who;
  54. End;
  55. Min:=Big;
  56. For I:=1 To N Do
  57. If Bo[I] And (Fr[I]>0) And (Dis[I]<Min) Then
  58. Begin
  59. Who:=I;
  60. Min:=Dis[I];
  61. End;
  62. Bo[Who]:=False;
  63. End;
  64. End;
  65. Procedure Print; {输出结果}
  66. Var
  67. I :Integer;
  68. Begin
  69. Assign(F,Outputfile);
  70. Rewrite(F);
  71. Writeln(F,Dis[1]);
  72. I:=1;
  73. While I<>N Do
  74. Begin
  75. Write(F,I,' ');
  76. I:=Fr[I];
  77. End;
  78. Writeln(F,N);
  79. Close(F);
  80. End;
  81. Begin
  82. Init; {输入}
  83. Main; {求解}
  84. Print; {输出}
  85. End.