给定n 个城市的集合{1，2, …,n}，旅行商从住地城市1出发，需要到城市2、3、…、n去推销商品，最后返回城市1，若任意两个城市间的距离已知，则该旅行商应如何选择其最佳行走路线，使得所走的路程最短?(注：TSP问题可以抽象为图模型，采用邻接矩阵作为存储结构) 输入格式: 有多组测试数据，每组数据的第一行为正整数n(2<n<10)，表示n个城市，接下来n行是网图的邻接矩阵，每行按点的编号从小到大的顺序输入n个整数xj(0<=xj<=500，或者xj=9999)表示行顶点i与列顶点j之间的距离，其中9999表示两顶点没有边，即两个顶点的距离为无穷。(注：边上带权的图称为网图，权值表示两个城市的距离) 输出格式: 对于每组数据，请在一行里输出旅行商所走的最短路程，如果不存在最短路程则输出"no exist"。给出多种代码方案

这是一个经典的旅行商问题，可以使用动态规划或者回溯法来解决。

动态规划解法：

假设dp[i][S]表示从城市1出发，已经走过集合S中的城市，最后到达城市i的最短距离。其中，S是一个二进制数，每个二进制位表示对应城市是否走过，例如S=101表示已经走过城市1和3，但是还没有走过城市2。

初始状态为dp[1][1]=0，表示从城市1出发到达城市1的距离为0。转移方程为dp[i][S]=min{dp[j][S-{i}]+dist[j][i]}，其中j是已经走过的城市，dist[j][i]表示从城市j到城市i的距离。

最终的答案为min{dp[i][(1<<n)-1]+dist[i][1]}，其中i表示最后一个到达的城市，(1<<n)-1表示所有城市都已经走过。

代码如下：

import sys

INF = 99999999

def tsp(n, dist):
    dp = [[INF] * (1<<n) for _ in range(n+1)]
    dp[1][1] = 0
    for S in range(1<<n):
        for i in range(2, n+1):
            if not (S & (1<<(i-1))):
                continue
            for j in range(1, n+1):
                if S & (1<<(j-1)):
                    dp[i][S] = min(dp[i][S], dp[j][S^(1<<(i-1))] + dist[j][i])
    ans = INF
    for i in range(2, n+1):
        ans = min(ans, dp[i][(1<<n)-1] + dist[i][1])
    if ans == INF:
        print("no exist")
    else:
        print(ans)

if __name__ == '__main__':
    while True:
        n = int(input())
        if n == 0:
            break
        dist = [[INF] * (n+1) for _ in range(n+1)]
        for i in range(1, n+1):
            line = list(map(int, input().split()))
            for j in range(1, n+1):
                if line[j-1] == 9999:
                    dist[i][j] = INF
                else:
                    dist[i][j] = line[j-1]
        tsp(n, dist)

回溯法解法：

回溯法的思路比较简单，就是枚举所有可能的路径，然后选取最短的路径作为答案。

具体来说，可以定义一个visited数组表示每个城市是否已经走过，然后从城市1开始进行深度优先搜索，每次搜索到一个城市时，标记visited数组，然后递归搜索下一个城市，直到所有城市都被走过，然后计算这条路径的距离，更新答案。最后返回最短路径的长度。

代码如下：

import sys

INF = 99999999

def tsp(n, dist):
    visited = [False] * (n+1)
    visited[1] = True
    ans = [INF]
    def dfs(curr, length, cnt):
        if cnt == n:
            ans[0] = min(ans[0], length + dist[curr][1])
            return
        if length >= ans[0]:
            return
        for i in range(1, n+1):
            if not visited[i]:
                visited[i] = True
                dfs(i, length+dist[curr][i], cnt+1)
                visited[i] = False
    dfs(1, 0, 1)
    if ans[0] == INF:
        print("no exist")
    else:
        print(ans[0])

if __name__ == '__main__':
    while True:
        n = int(input())
        if n == 0:
            break
        dist = [[INF] * (n+1) for _ in range(n+1)]
        for i in range(1, n+1):
            line = list(map(int, input().split()))
            for j in range(1, n+1):
                if line[j-1] == 9999:
                    dist[i][j] = INF
                else:
                    dist[i][j] = line[j-1]
        tsp(n, dist)

这两种方法的时间复杂度都是O(n^22^n)，在实际应用中，对于大规模的数据，可能会超时。可以使用一些优化技巧，例如剪枝等，来提高效率。