牛客多校第一场H题

**牛客多校第一场H题**

**题目描述**

给定一个图，求出从源点到每个其他顶点的最短距离。图中可能存在负权边。

**输入格式**

第1 行：两个整数 n 和 m（n 为顶点数，m 为边数）。

第2 到 (m+1) 行：每行描述一条边，格式为 u v w，其中 u 和 v 是顶点编号，w 是边权。

**输出格式**

从源点到每个其他顶点的最短距离（如果不存在负环，则为正整数）。

**代码实现**

import sysdef read_int():
 return int(sys.stdin.readline().strip())

def read_ints():
 return list(map(int, sys.stdin.readline().split()))

def BellmanFord(n, edges):
 dis = [float('inf')] * n dis[0] =0 # 源点距离为0 for _ in range(n -1): # 最多 n-1 次更新 for u, v, w in edges:
 if dis[u] != float('inf') and dis[u] + w < dis[v]:
 dis[v] = dis[u] + w return disn, m = read_ints()
edges = []
for _ in range(m):
 u, v, w = read_ints()
 edges.append((u -1, v -1, w)) # 将顶点编号减1dis = BellmanFord(n, edges)
print(' '.join(map(str, dis[1:]))) # 输出从源点到每个其他顶点的最短距离

**注释**

* `BellmanFord` 函数实现了贝尔曼-福特算法，用于求出从源点到每个其他顶点的最短距离。
* `read_int` 和 `read_ints` 函数用于读取输入数据。
* `edges` 列表存储图中的边信息，每条边由三个元素组成：起始顶点、终止顶点和边权。
* `dis` 列表存储从源点到每个其他顶点的最短距离，初始值为无穷大。

**时间复杂度**

*读取输入数据的时间复杂度为 O(m)，其中 m 是边数。
* `BellmanFord` 函数的时间复杂度为 O(nm)。
* 总体而言，算法的时间复杂度为 O(nm)。

**空间复杂度**

* `edges` 列表存储图中的边信息，空间复杂度为 O(m)。
* `dis` 列表存储从源点到每个其他顶点的最短距离，空间复杂度为 O(n)。
* 总体而言，算法的空间复杂度为 O(n + m)。