Pro_1_1.pas 2.0 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
  1. Program Pro_1_1; {用搜索算法解决例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. Qiu,Pr :Array[1..Max] Of Byte; {最短路径的数组}
  13. F :Text; {文件变量}
  14. Lp :Integer; {最短路径的城市数}
  15. N,M :Integer; {输入的数据}
  16. Min :Longint; {最短路径的长度}
  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 Search(Dep:Byte;Al:Longint); {寻找最短路径}
  37. Var
  38. I :Byte;
  39. Begin
  40. If Al>=Min Then Exit; {砍枝条件}
  41. If Qiu[Dep-1]=N Then {如果比当前还小,记录}
  42. Begin
  43. Min:=Al;
  44. Pr:=Qiu;
  45. Lp:=Dep-1;
  46. End
  47. Else
  48. For I:=2 To N Do {访问所有没访问过的城市}
  49. If (I In Se) And (Map[Qiu[Dep-1]]^[I]>0) Then
  50. Begin
  51. Exclude(Se,I);
  52. Qiu[Dep]:=I;
  53. Search(Dep+1,Al+Map[Qiu[Dep-1]]^[Qiu[Dep]]);
  54. Include(Se,I);
  55. End;
  56. End;
  57. Procedure Print; {输出数据}
  58. Var
  59. I :Integer;
  60. Begin
  61. Assign(F,Outputfile);
  62. Rewrite(F);
  63. Writeln(F,Min);
  64. For I:=1 To Lp Do
  65. Write(F,Pr[I],' ');
  66. Close(F);
  67. End;
  68. Begin
  69. Init; {输入数据}
  70. Se:=[2..N]; {各项值初始化}
  71. Qiu[1]:=1;
  72. Min:=Big;
  73. Search(2,0); {寻找最短路径}
  74. Print; {输出}
  75. End.