"""Owned all-reachable Dijkstra ledger, simple finite digraph, integer costs."""
import heapq,itertools,json
from collections import deque
def validate(G):
    for u,edges in G.items():
        if len({v for v,c in edges})!=len(edges):raise ValueError('parallel edges outside subset')
        for v,c in edges:
            if v not in G or type(c)is not int or c<0:raise ValueError('known destination/nonnegative integer cost required')
def dijkstra(G,start):
    validate(G)
    if start not in G:raise ValueError('unknown source')
    count=itertools.count();heap=[(0,next(count),start)];best={start:0};parent={start:None};settled={};events=[]
    while heap:
        d,_,u=heapq.heappop(heap)
        if d!=best[u]:events.append({'event':'stale_pop','node':u,'queued':d,'best':best[u]});continue
        if u in settled:continue
        settled[u]=d;events.append({'event':'settle','node':u,'distance':d})
        for v,w in G[u]:
            candidate=d+w
            if v not in best or candidate<best[v]:
                old=best.get(v);best[v]=candidate;parent[v]=u;heapq.heappush(heap,(candidate,next(count),v));events.append({'event':'improve','from':u,'to':v,'old':old,'new':candidate})
    routes={}
    for target in G:
        if target not in settled:routes[target]=None;continue
        route=[];u=target
        while u is not None:route.append(u);u=parent[u]
        routes[target]=list(reversed(route))
    return {'distances':{u:settled.get(u) for u in G},'parents':{u:parent.get(u) for u in G},'routes':routes,'events':events}
def enumerate_costs(G,start,target):
    vals=[]
    def walk(u,path,cost):
        if u==target:vals.append(cost);return
        for v,w in G[u]:
            if v not in path:walk(v,path+[v],cost+w)
    walk(start,[start],0);return vals
def bfs_route(G,start,target):
    queue=deque([[start]]);seen={start}
    while queue:
        path=queue.popleft();u=path[-1]
        if u==target:return path
        for v,w in G[u]:
            if v not in seen:seen.add(v);queue.append(path+[v])
    return None
def path_cost(G,p):return sum(next(w for v,w in G[a] if v==b) for a,b in zip(p,p[1:]))
def demo():
    G={'S':[('A',7),('B',2),('G',10)],'A':[('G',2)],'B':[('A',1),('C',0)],'C':[('A',1),('G',8)],'G':[],'U':[]};out=dijkstra(G,'S')
    oracle={u:min(enumerate_costs(G,'S',u),default=None) for u in G};assert out['distances']==oracle=={'S':0,'A':3,'B':2,'C':2,'G':5,'U':None}
    for u,p in out['routes'].items():
        if p is not None:assert path_cost(G,p)==out['distances'][u]
    stale=[e['node'] for e in out['events'] if e['event']=='stale_pop'];assert stale==['A','G']
    bfs=bfs_route(G,'S','G');assert bfs==['S','G'] and path_cost(G,bfs)==10 and out['routes']['G']==['S','B','A','G']
    try:dijkstra(G|{'U':[('S',-1)]},'S')
    except ValueError:rejected=True
    else:raise AssertionError('unreachable negative edge ignored')
    return {'authored_graph':G,'tie_policy':'insertion counter; neighbor list order; equal candidate retains parent','all_reachable_run':out,'independent_simple_path_min_cost_oracle':oracle,'stale_nodes_actually_popped':stale,'BFS_ignoring_weights_route':bfs,'BFS_route_total_weight':path_cost(G,bfs),'negative_edge_on_unreachable_node_rejected_before_search':rejected,'NetworkX_or_real_routing_executed':False}
if __name__=='__main__':print(json.dumps(demo(),indent=2))