•输入样例: 7 10 1,2,17 1,3,8 1,4,22 2,5,13 3,4,8 3,6,20 4,5,9 4,7,19 5,7,12 6,7,16 •输出样例: 1 3 4 3 6 7 5 2 1 102
时间: 2023-07-02 09:08:02 浏览: 54
这是一个最短路径问题,输入的第一行给出了总节点数 n 和边数 m,接下来 m 行每行给出一条边的两个端点和边权。我们需要求出从节点1到节点n的最短路径以及其长度。
可以使用 Dijkstra 算法来解决这个问题。Dijkstra 算法的基本思想是维护一个距离起点已知最短路径的节点集合 S,初始时将起点加入 S。然后每次从 S 中选取一个距离起点最近的节点 u,更新与 u 相邻的节点的距离,并将这些节点加入 S。重复这个过程直到 n 被加入 S 或者 S 中已经没有节点。
具体实现细节可以参考下面的代码:
```python
import heapq
INF = float('inf')
n, m = map(int, input().split())
# 构建邻接表
adj = [[] for _ in range(n)]
for _ in range(m):
u, v, w = map(int, input().split())
adj[u-1].append((v-1, w))
adj[v-1].append((u-1, w))
# 初始化距离数组
dist = [INF] * n
dist[0] = 0
# 使用堆优化的 Dijkstra 算法
heap = [(0, 0)]
while heap:
d, u = heapq.heappop(heap)
if dist[u] < d: # 如果当前节点已经被更新过了,就跳过
continue
if u == n-1: # 如果已经到达终点,就退出循环
break
for v, w in adj[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
# 输出最短路径和长度
if dist[n-1] < INF:
path = [n]
u = n-1
while u != 0:
for v, w in adj[u]:
if dist[v] + w == dist[u]:
path.append(v+1)
u = v
break
path.reverse()
print(' '.join(map(str, path)), dist[n-1])
else:
print(-1)
```
在上面的代码中,我们使用了一个 dist 数组来记录每个节点到起点的距离,在算法开始时将其初始化为正无穷,除了起点 dist[0] = 0。堆 heap 存储了每个节点的距离和编号,我们每次从堆中弹出一个距离最小的节点 u,然后遍历 u 的所有邻居节点 v,如果从起点到 v 的距离可以通过 u 更新,就将 dist[v] 更新为 dist[u] + w,并将 (dist[v], v) 加入堆中。这样,每次从堆中弹出的节点都是距离起点最近的节点,直到堆中没有节点或者终点被加入 S。
最后,如果 dist[n-1] < INF,说明存在一条从起点到终点的路径,我们可以通过回溯 dist 数组和邻接表 adj 来构造这条路径,并输出路径和长度。否则,说明不存在这样的路径,输出 -1。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)