from __future__ import annotations
from typing import List
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

def solve_tsp(time_matrix: List[List[float]]) -> List[int]:
    """
    OSRMのduration行列（秒）を入力に、0番ノード（Start）発→全訪問→Start戻りの巡回順序を返す。
    OR-Toolsで解けない場合は貪欲法でフォールバックします。
    返り値例: [0, 3, 2, 1, 0]
    """
    n = len(time_matrix) if time_matrix else 0
    if n <= 1:
        return list(range(n))

    # 行列のサニタイズ（Noneや欠損を大値に、対角は0、int秒へ）
    BIG = 10**9
    matrix: List[List[int]] = []
    for i in range(n):
        row_i = []
        for j in range(n):
            try:
                v = time_matrix[i][j]
                v = float(v) if v is not None else BIG
            except Exception:
                v = BIG
            if i == j:
                v = 0.0
            row_i.append(int(max(0, round(v))))
        matrix.append(row_i)

    # OR-Tools セットアップ
    manager = pywrapcp.RoutingIndexManager(n, 1, 0)  # depot=0
    routing = pywrapcp.RoutingModel(manager)

    def transit_cb(from_index, to_index):
        i = manager.IndexToNode(from_index)
        j = manager.IndexToNode(to_index)
        return matrix[i][j]

    transit_idx = routing.RegisterTransitCallback(transit_cb)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)

    params = pywrapcp.DefaultRoutingSearchParameters()
    params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    params.time_limit.FromSeconds(1)  # 1秒で切り上げ（HF Spaces向けに軽量）

    solution = routing.SolveWithParameters(params)
    if solution:
        index = routing.Start(0)
        order: List[int] = []
        while not routing.IsEnd(index):
            order.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
        order.append(manager.IndexToNode(index))  # 最後にdepot(0)へ戻る
        return order

    # フォールバック：近傍貪欲
    unvisited = set(range(1, n))
    order = [0]
    cur = 0
    while unvisited:
        nxt = min(unvisited, key=lambda j: matrix[cur][j])
        order.append(nxt)
        unvisited.remove(nxt)
        cur = nxt
    order.append(0)
    return order