"""Owned finite-graph A* with reopened improved nodes and an exhaustive simple-path oracle."""
import heapq,itertools,json,math
def validate(G,h,goal):
    if goal not in G or set(h)!=set(G) or h[goal]!=0:raise ValueError('complete fixed heuristic and h(goal)=0')
    if any(type(v)not in (int,float) or not math.isfinite(v) or v<0 for v in h.values()):raise ValueError('finite nonnegative heuristic')
    for edges in G.values():
        for v,c in edges:
            if v not in G or type(c)not in (int,float) or not math.isfinite(c) or c<0:raise ValueError('finite nonnegative edge costs')
def paths(G,start,goal):
    out=[]
    def walk(u,path,cost):
        if u==goal:out.append((cost,path));return
        for v,w in G[u]:
            if v not in path:walk(v,path+[v],cost+w)
    walk(start,[start],0);return out
def astar(G,start,goal,h):
    validate(G,h,goal);counter=itertools.count();heap=[(h[start],next(counter),start,0)];best={start:0};parent={start:None};expanded={};trace=[];reopened=[]
    while heap:
        f,_,u,g=heapq.heappop(heap)
        if g!=best[u]:trace.append({'event':'stale_skip','node':u,'queued_g':g,'best_g':best[u]});continue
        if u in expanded and g>=expanded[u]:continue
        if u in expanded:reopened.append(u)
        expanded[u]=g;trace.append({'event':'expand','node':u,'g':g,'h':h[u],'f':f})
        if u==goal:
            route=[];v=u
            while v is not None:route.append(v);v=parent[v]
            return {'path':list(reversed(route)),'cost':g,'trace':trace,'reopened_nodes':reopened}
        for v,w in G[u]:
            cand=g+w
            if cand<best.get(v,math.inf):
                old=best.get(v);best[v]=cand;parent[v]=u;heapq.heappush(heap,(cand+h[v],next(counter),v,cand));trace.append({'event':'improve','from':u,'to':v,'old_g':old,'new_g':cand,'new_f':cand+h[v]})
    return {'path':None,'cost':None,'trace':trace,'reopened_nodes':reopened}
def demo():
    G={'S':[('A',3),('B',1)],'A':[('G',3)],'B':[('A',1),('G',10)],'G':[],'U':[]}
    h={'S':0,'A':0,'B':4,'G':0,'U':0};oracle=min(paths(G,'S','G'));true_costs={u:min((c for c,p in paths(G,u,'G')),default=None) for u in G}
    assert all(h[u]<=d for u,d in true_costs.items() if d is not None)
    inconsistent=[(u,v) for u,es in G.items() for v,w in es if h[u]>w+h[v]];assert inconsistent==[('B','A')]
    good=astar(G,'S','G',h);bad=astar(G,'S','G',h|{'B':100});zero=astar(G,'S','G',{u:0 for u in G});missing=astar(G,'S','U',{u:0 for u in G})
    assert good['cost']==zero['cost']==oracle[0]==5 and good['path']==['S','B','A','G'] and good['reopened_nodes']==['A']
    assert bad['cost']==6 and bad['cost']>oracle[0] and missing['path']is None
    return {'authored_graph':G,'tie_policy':'heap insertion counter; neighbor list order; equal g does not replace parent','fixed_admissible_inconsistent_h':h,'true_remaining_costs_by_simple_path_oracle':true_costs,'inconsistent_edges':inconsistent,'all_simple_goal_paths':paths(G,'S','G'),'valid_reopening_run':good,'overestimating_h_B100_run':bad,'zero_heuristic_run':zero,'unreachable_target_run':missing,'NetworkX_or_real_route_search_executed':False}
if __name__=='__main__':print(json.dumps(demo(),indent=2))