from heapq import heappop, heappush

def a_star(graph, start, goal, heuristics):
    open_set = [(heuristics[start], 0, start, [start])]  # (f = g + h, g, node, path)
    visited = set()

    while open_set:
        f, cost_so_far, current, path = heappop(open_set)

        if current == goal:
            return path, cost_so_far

        if current in visited:
            continue
        visited.add(current)

        for neighbor, edge_cost in graph.get(current, []):
            if neighbor not in visited:
                g = cost_so_far + edge_cost
                h = heuristics.get(neighbor, float('inf'))
                heappush(open_set, (g + h, g, neighbor, path + [neighbor]))

    return None, None

# Sample graph
graph = {
    "kavali": [("ongole", 40), ("nellore", 50)],
    "ongole": [("guntur", 70)],
    "nellore": [("tirupati", 130)],
    "guntur": [],
    "tirupati": []
}

# Heuristics (straight-line distance or estimated cost to goal)
heuristics = {
    "kavali": 100,
    "ongole": 80,
    "nellore": 60,
    "guntur": 50,
    "tirupati": 0
}

# Input
start_city = "kavali"
goal_city = "tirupati"

# Run A*
path, total_cost = a_star(graph, start_city, goal_city, heuristics)

# Output
if path:
    print("Path:", " -> ".join(path))
    print("Total cost:", total_cost)
else:
    print("No path found.")