给定n 个城市的集合{1，2, …,n}，旅行商从住地城市1出发，需要到城市2、3、…、n去推销商品，最后返回城市1，若任意两个城市间的距离已知，则该旅行商应如何选择其最佳行走路线，使得所走的路程最短?(注：TSP问题可以抽象为图模型，采用邻接矩阵作为存储结构) 输入格式: 有多组测试数据，每组数据的第一行为正整数n(2<n<10)，表示n个城市，接下来n行是网图的邻接矩阵，每行按点的编号从小到大的顺序输入n个整数xj100） 输出格式: 每组输出占一行，若背包有物品，输出其价值；若背包为空则输出0。

这是一个典型的旅行商问题（TSP问题），可以用动态规划来解决。设dp[S][i]表示已经走过的城市集合为S，当前在城市i的最短路程。则有状态转移方程：

dp[S][i] = min(dp[S-{i}][j] + dist[j][i])，其中j∈S-{i}

其中，dist[j][i]表示城市j到城市i之间的距离。

最终的答案为dp[{1,2,3,...,n}][1]，即从城市1出发，到达所有城市，最后回到城市1的最短路程。

下面是一个Python实现：

INF = float('inf')

while True:
    try:
        n = int(input())
        graph = [list(map(int, input().split())) for _ in range(n)]

        # 初始化状态
        dp = [[INF] * n for _ in range(1<<n)]
        for i in range(n):
            dp[1<<i][i] = 0

        # 状态转移
        for s in range(1<<n):
            for i in range(n):
                if not (s&(1<<i)):  # 如果i不在集合S中
                    continue
                for j in range(n):
                    if s&(1<<j):  # 如果j在集合S中
                        dp[s][i] = min(dp[s][i], dp[s-(1<<i)][j] + graph[j][i])

        # 输出结果
        print(dp[(1<<n)-1][0])

    except:
        break

注意要使用try-except，因为可能会有多组数据。