import heapq
from math import isfinite

cities = input("Enter at least 8 unique city names, separated by spaces: ").split()
if len(cities) < 8 or len(set(cities)) != len(cities):
    raise ValueError("Enter at least 8 distinct city names (use underscores within a name).")
graph = {city: [] for city in cities}

edge_count = int(input("Number of undirected roads: "))
if edge_count < 0:
    raise ValueError("Number of roads cannot be negative.")
print("Enter each road as: city1 city2 distance")
for _ in range(edge_count):
    a, b, distance = input("Road: ").split()
    distance = float(distance)
    if a not in graph or b not in graph or not isfinite(distance) or distance < 0:
        raise ValueError("Use listed cities and finite, nonnegative distances.")
    graph[a].append((b, distance))
    graph[b].append((a, distance))

source = input("Source city: ").strip()
goal = input("Destination city: ").strip()
if source not in graph or goal not in graph:
    raise ValueError("Source and destination must be listed cities.")

print("Enter heuristic estimates to the destination; Enter uses 0.")
print("For A*, never overestimate the true remaining distance; 0 is always admissible.")
heuristics = {}
for city in cities:
    value = float(input(f"h({city}): ").strip() or "0")
    if not isfinite(value) or value < 0:
        raise ValueError("Heuristics must be finite and nonnegative.")
    heuristics[city] = value
if heuristics[goal] != 0:
    raise ValueError("The destination heuristic must be 0.")

def h(city):
    return heuristics[city]

# Queue item: (heuristic only, city, route, actual cost)
queue = [(h(source), source, [source], 0)]
visited = set()
found = False

while queue:
    estimate, city, path, cost = heapq.heappop(queue)
    if city in visited:
        continue
    visited.add(city)
    if city == goal:
        print("Selected route:", " -> ".join(path))
        print("Actual path cost:", cost)
        found = True
        break
    for neighbour, distance in graph[city]:
        if neighbour not in visited:
            heapq.heappush(queue, (h(neighbour), neighbour,
                                  path+[neighbour], cost+distance))

if not found:
    print("No route exists.")
print("Nodes explored:", len(visited))
