输入格式: 有多组测试数据,每组数据的第一行为正整数n(2<n<10),表示n个城市,接下来n行是网图的邻接矩阵,每行按点的编号从小到大的顺序输入n个整数xj(0<=xj<=500,或者xj=9999),表示行顶点i与列顶点j之间的距离,其中9999表示两顶点没有边,即两个顶点的距离为无穷。(注:边上带权的图称为网图,权值表示两个城市的距离) 输出格式: 对于每组数据,请在一行里输出旅行商所走的最短路程,如果不存在最短路程则输出"no exist"。
时间: 2024-02-25 21:58:43 浏览: 46
好的,这个问题与上一个问题的区别在于输入格式,但解题思路是一样的。
下面是一个Python实现:
```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) and graph[j][i] != 9999: # 如果j在集合S中且有边相连
dp[s][i] = min(dp[s][i], dp[s-(1<<i)][j] + graph[j][i])
# 输出结果
ans = INF
for i in range(n):
if graph[i][0] != 9999: # 如果0号城市与i号城市有边相连
ans = min(ans, dp[(1<<n)-1][i] + graph[i][0])
if ans != INF:
print(ans)
else:
print("no exist")
except:
break
```
注意要使用try-except,因为可能会有多组数据。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)