pastebin

pastebin

Paste Search Dynamic
Recent pastes
printArray
  1. b = [true];
  2. x = [0];
  3. y = [0];
  4. z = [0];
  5.  
  6.  
  7. # raw =  [    [0,3,14,18,15],
  8. #             [3,0,4,22,20],
  9. #             [17,9,0,16,4],
  10. #             [9,20,7,0,18],
  11. #             [9,15,11,5,0]       ]
  12.  
  13. # raw =[[0  , 6 ,  6 ,  4],
  14. #         [6,   0  , 4 ,  6],
  15. #         [6,   4  , 0 ,  7],
  16. #         [4  , 6  , 7 ,  0]]
  17. def printArray(a):
  18.     print("Solution{:3d}".format(num),end="")
  19.     print(":",end=" " )
  20.     for i in range(1, n + 1):
  21.         print("{:4d}".format(a[i]-1), end="")
  22.     print()
  23.  
  24.  
  25. def count(k, buocdi, luotdi):
  26.     if (buocdi < x[0]):
  27.         for i in range(1, n + 1):
  28.             if (b[i] and buocdi < x[0]):
  29.                 x[k] = i  # raw[i-1][k-1]
  30.                 z[k] = x[k - 1]
  31.                 luotdi += 1
  32.                 if (k != 1):
  33.                     buocdi += raw[z[k] - 1][i - 1]
  34.                 if (k == n):
  35.                     buocdi += raw[x[k] - 1][x[1]-1]
  36.                     if (buocdi < x[0]):
  37.                         x[0] = buocdi
  38.                 else:
  39.                     b[i] = false
  40.                     if (buocdi < x[0]):
  41.                         count(k + 1, buocdi, luotdi)
  42.                     if (k != 1):
  43.                         buocdi -= raw[z[k] - 1][i - 1]
  44.                     b[i] = true
  45.  
  46. def printRes(k, buocdi, luotdi):
  47.     try:
  48.         if (buocdi <= mindis):
  49.             # print("Bước đi hiện tại đang nhỏ hơn bước đi cơ sở",buocdi,x[0])
  50.             for i in range(1, n + 1):
  51.                 if (b[i] and buocdi <= mindis):
  52.                     x[k] = i  # raw[i-1][k-1]
  53.                     z[k] = x[k - 1]
  54.                     luotdi += 1
  55.                     if (k!=1):
  56.                         buocdi += raw[z[k] - 1][i - 1]
  57.                     if (k == n):
  58.                         # print("Ô cuối cùng ở vị trí: ",x[k],x[1],end=" ")
  59.                         # print("Giá trị",raw[x[k] - 1][x[1]-1])
  60.                         buocdi += raw[x[k] - 1][x[1]-1]
  61.  
  62.                         # printArray(x)
  63.                         # print("Fake",buocdi)
  64.                         # print()
  65.                         if (buocdi == mindis):
  66.                             global num
  67.                             num+=1
  68.                             printArray(x)
  69.                             # print("Real: ",buocdi)
  70.                     else:
  71.                         b[i] = false
  72.                         if (buocdi <= mindis):
  73.                             printRes(k + 1, buocdi, luotdi)
  74.                         if (k != 1):
  75.                             buocdi -= raw[z[k] - 1][i - 1]
  76.                         b[i] = true
  77.     except:
  78.         print("Solution 1: 0")
  79.  
  80. n = int(input())
  81. raw = []
  82. for i in range(0, n):
  83.     raw.append([int(x) for x in input().split()])
  84.  
  85. for i in range(1, n + 1):
  86.     b.append(true)
  87.     x.append(1)
  88.     z.append(0)
  89. global num
  90. num=0
  91. x[0] = 9999999999999999999999999999999999999999999999999999999999999999
  92. count(1, 0, 0)
  93. if n == 1:
  94.     x[0] = raw[0][0]
  95. mindis = x[0]
  96. # x[0]=1
  97. print("Min total distance =",mindis)
  98.  
  99. printRes(1, 0, 0)
  100.  
Parsed in 0.042 seconds