【问题描述】 给定n个城市(从0到n-1),3元组[A, B, C]表示城市A和城市B之间存在道路,且成本为C。计算从0号城市出发,旅行完每个城市一遍,最后回到0号城市的最小成本与路径。如果不存在最优方案,输出-1. 【输入形式】 第一行有两个数n、m表示n个城市,m条边。 接下来的m行均为空格隔开的三个整数A B C,表示城市A和B之间的成本为C 【输出形式】 最小成本 最小成本对应的路径 根据以上部分给出其代码
时间: 2023-11-27 20:54:34 浏览: 44
以下是使用Python实现的代码,使用了Dijkstra算法和回溯法:
```python
import heapq
class Graph:
def __init__(self, n):
self.n = n
self.adj = [[] for _ in range(n)]
def add_edge(self, u, v, w):
self.adj[u].append((v, w))
self.adj[v].append((u, w))
def dijkstra(self, start):
dist = [float('inf')] * self.n
dist[start] = 0
heap = [(0, start)]
prev = [-1] * self.n
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in self.adj[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
return dist, prev
def get_path(self, end, prev):
path = []
while end != -1:
path.append(end)
end = prev[end]
return path[::-1]
def solve(self):
# 从0号城市开始遍历
dist, prev = self.dijkstra(0)
if dist[0] == float('inf'):
return -1, []
# 从终点开始回溯,构造最优路径
path = self.get_path(0, prev) + [0]
if len(path) != self.n:
return -1, []
return dist[0], path
n, m = map(int, input().split())
g = Graph(n)
for i in range(m):
u, v, w = map(int, input().split())
g.add_edge(u, v, w)
cost, path = g.solve()
if cost == -1:
print(cost)
else:
print(cost)
print(' '.join(str(x) for x in path))
```
其中,`Graph`类表示图,使用邻接表存储图。在`dijkstra`方法中,使用堆优化的Dijkstra算法求解单源最短路径,同时记录每个节点的前驱节点,方便回溯最优路径。在`get_path`方法中,从终点开始回溯,构造最优路径。最后,在`solve`方法中,先求出从0号城市出发到其他城市的最短距离,如果存在无法遍历完所有城市的情况,返回-1;否则,从终点开始回溯,构造最优路径,并返回最小成本和最小成本对应的路径。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)