fork download
copy 
  1. def f(G,s):
  2.  q,C,K=[({0},{j for k in G for j in k}-{0},[])],[],[]
  3.  for n,u,p in q:
  4.   C+=sum(G.get((x,y),0)for x in n for y in u),
  5.   for N in n:
  6.    for i in G:
  7.     if(i[0]==N)>(i in p)<(i[1]!=s)>((T:=sorted(p+[i]))in K):q+=({*n,*i},u-{*i},p+[i]),;K+=T,
  8.  return min(C)
  9.  
  10. def to_edges(m):
  11. 	return {(x, y):m[x][y] for x in range(len(m))for y in range(len(m[0]))if m[x][y]},len(m)-1
  12.  
  13. m1 = [[ 0, 20,  0, 50,  0,  0],
  14.  [ 0,  0, 40, 10,  0,  0],
  15.  [ 0,  0,  0,  0, 25, 25],
  16.  [ 0,  0, 45,  0, 30,  0],
  17.  [ 0,  0,  0,  0,  0, 50],
  18.  [ 0,  0,  0,  0,  0,  0]]
  19.  
  20. m2 = [[ 0, 10, 17,  0,  0,  0,  0],
  21.  [ 0,  0,  0,  2, 13,  0,  0],
  22.  [ 0,  5,  0,  0,  4,  8,  0],
  23.  [ 0,  0,  0,  0,  0,  0, 20],
  24.  [ 0,  0,  0, 18,  0,  0,  0],
  25.  [ 0,  0,  0,  0,  1,  0,  7],
  26.  [ 0,  0,  0,  0,  0,  0,  0]]
  27.  
  28. m3 = [[ 0,  6,  2,  7,  4,  0,  0,  0],
  29.  [ 0,  0,  0,  0,  0, 10,  0,  0],
  30.  [ 0,  8,  0,  0,  0,  0,  9,  4],
  31.  [ 0,  0, 11,  0,  0,  0,  0,  0],
  32.  [ 0,  0,  0,  5,  0,  0,  0,  0],
  33.  [ 0,  0, 13,  0,  0,  0,  0, 16],
  34.  [ 0,  0,  0, 14,  0,  0,  0, 12],
  35.  [ 0,  0,  0,  0,  0,  0,  0,  0]]
  36.  
  37. m4 = [[ 0, 40, 50,  0,  0,  0,  0,  0,  0],
  38.  [ 0,  0,  0, 30, 10,  0,  0,  0,  0],
  39.  [ 0,  0,  0, 40,  0,  0, 10,  0,  0],
  40.  [ 0,  0,  0,  0, 15, 10,  0,  0,  0],
  41.  [ 0,  0,  0,  0,  0,  0,  0,  0, 20],
  42.  [ 0,  0,  0,  0,  0,  0, 15, 20,  0],
  43.  [ 0,  0,  0,  0,  0,  0,  0, 30,  0],
  44.  [ 0,  0,  0,  0,  0,  0,  0,  0, 50],
  45.  [ 0,  0,  0,  0,  0,  0,  0,  0,  0]]
  46.  
  47. m5 = [[ 0, 5, 8, 3, 3, 7, 0, 0, 0, 7],
  48.  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 4],
  49.  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 9],
  50.  [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
  51.  [ 0, 0, 0, 0, 0, 0, 0, 4, 0, 0],
  52.  [ 0, 0, 0, 0, 0, 0, 0, 0, 6, 0],
  53.  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
  54.  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 6],
  55.  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 5],
  56.  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
  57.  
  58. m6 = [[0, 5],
  59.  [0, 0]]
  60.  
  61. print(f(*to_edges(m1)))
  62. print(f(*to_edges(m2)))
  63. print(f(*to_edges(m3)))
  64. print(f(*to_edges(m4)))
  65. print(f(*to_edges(m5)))
  66. print(f(*to_edges(m6)))
Success #stdin #stdout 0.12s 13972KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
70
27
19
40
28
5
https://ideone.com/uUW2tL
language:
Python 3 (python  3.12)
created:
2 hours 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!