pta9-1 成都地铁路径规划

### 成都地铁路径规划算法实现

#### 动态规划解决Hamilton路径问题

对于给定的一张 \( n \) (\( n\leq20 \))个点的带权无向图，其中点从 0 至 \( n-1 \) 进行编号。目标在于寻找由起点 0 到达终点 \( n-1 \) 的最短Hamilton路径，即一条能够不重复也不遗漏地遍历每一个顶点仅一次的道路[^1]。

为了处理这个问题，可以采用动态规划的方法。创建一个三维数组 `dp` 来存储状态转移方程的结果，这里 `dp[mask][i]` 表示当前访问过的节点集合为 `mask` 并且最后到达的是第 i 个节点时所累积的成本最低是多少。初始条件设置为当只访问过第一个节点（也就是源节点）的时候成本为零；其他情况下默认值设为无穷大表示尚未计算的状态。

在每次迭代过程中更新未被标记过的邻接节点，并记录下新的更优解直到所有的可能性都被探索完毕为止。最终返回 dp 数组中代表全部节点均已被访问并终止于最后一个节点的那一项作为结果输出即可得到所需的最短汉密尔顿路径长度。

下面是具体的Python代码实现：

import sys

def shortest_hamilton_path(n, edges):
    INF = float('inf')
    
    # 初始化距离矩阵dist和dp表
    dist = [[INF]*n for _ in range(n)]
    for u,v,w in edges:
        dist[u][v]=w
        dist[v][u]=w
    
    mask_size = 1 << n 
    dp = [[INF]*n for _ in range(mask_size)]  
    dp[1][0] = 0 
    
    # 填充DP表格
    for mask in range(1<<n):   
        for j in range(n):     
            if (mask >> j)&1==0: continue      
            prev_mask = mask ^ (1<<j)
            
            for k in range(n):       
                if ((prev_mask>>k)&1)==0 or k == j :continue
                
                cost = dp[prev_mask][k]+dist[k][j]
                
                if cost<dp[mask][j]:
                    dp[mask][j]=cost
                    
    result = min(dp[(1<<n)-1])
    
    return -1 if result == INF else result


if __name__=="__main__":
    while True:
        try:
            N,M=list(map(int,input().split()))
            if not(N and M):break
            
            edge_list=[]
            for m in range(M):
                A,B,C=map(int,input().split())
                edge_list.append((A-1,B-1,C))
                
            print(shortest_hamilton_path(N,edge_list))

        except EOFError:
            break

此段代码实现了基于动态规划思想求解最短Hamilton路径的功能，在输入部分模拟了多实例测试环境下的读取操作以便适应不同规模的数据集需求。