fork download 
  1. nodes={0:[1],1:[2],2:[3],3:[4,5,6,7,8]}
  2. PB={}
  3. NB={}
  4. def below(i):
  5.     if i not in nodes:
  6.         PB[i]=0
  7.         NB[i]=1
  8.         return 0,1
  9.     tot_nodes_below=0
  10.     tot_paths_below=0
  11.     for node in nodes[i]:
  12.         paths_below,nodes_below=below(node)
  13.         tot_nodes_below+=nodes_below
  14.         tot_paths_below+=paths_below
  15.     tot_paths_below+=tot_nodes_below
  16.     tot_nodes_below+=1
  17.     PB[i]=tot_paths_below
  18.     NB[i]=tot_nodes_below
  19.     return tot_paths_below,tot_nodes_below
  20.  
  21. P={0:below(0)[0]}
  22. def fill_P(i):
  23.     for node in nodes[i]:
  24.         P[node]=P[i]+9-2*NB[node] #7 is the number of nodes
  25.         if node in nodes:
  26.             fill_P(node)
  27. fill_P(0)
  28.  
  29. _min=min(P.values())
  30. answers=[k for k in P if P[k]==_min]
  31. print answers
Success #stdin #stdout 0.02s 6660KB
comments (?)
stdin 
Standard input is empty
stdout 
[3]
https://ideone.com/W6lnF
language:
Python (cpython 2.7.16)
created:
14 years 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!