fork download
copy 
  1. n = 0
  2. m = []
  3. cMin = float('inf')  
  4. fmin = float('inf')
  5. path = 0
  6. visited = []
  7.  
  8. def Try(k, pos):
  9.     global fmin, path, visited, m, n, cMin
  10.     if k == n:
  11.         current_total_path = path + m[pos][0]
  12.         if fmin > current_total_path:
  13.             fmin = current_total_path
  14.         return
  15.  
  16.     for i in range(1, n): 
  17.         if not visited[i]:
  18.             path += m[pos][i]
  19.             visited[i] = True
  20.             if path + cMin * (n-k) <= fmin:
  21.                 Try(k + 1, i)
  22.             visited[i] = False
  23.             path -= m[pos][i]
  24.  
  25. def main():
  26.     global n, m, cMin, fmin, visited 
  27.  
  28.     n = int(input())
  29.     visited = [False] * n  
  30.     m = [list(map(int, input().split())) for _ in range(n)]
  31.  
  32.     for i in range(n):
  33.         for j in range(n):
  34.             if i != j and m[i][j] < cMin:
  35.                 cMin = m[i][j]
  36.  
  37.     visited[0] = True 
  38.     Try(1, 0) 
  39.  
  40.     print(fmin)
  41.  
  42. main()
Success #stdin #stdout 0.11s 14084KB
comments (?)
stdin
copy 
4
0 1 1 9
1 0 9 3
1 9 0 2
9 3 2 0
stdout
copy 
7
https://ideone.com/4gn7Is
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!