给一个 n(1≤n≤10^6 ) 个点 m(1≤m≤10^6 ) 条边的无向图，求 s 到 t 的最短路的长度。 数据保证，s 出发可以到达 t,请从 stdin 读入。注意，输入可能很大 (>10MB) 第一行为四个正整数 n,m,s,t。 第二行起 m 行，每行三个非负整数 ui​,vi​,wi​(0≤wi​≤1)，表示从 ui​ 到 vi​ 有一条权值为 wi​ 的无向边。Time Limit: 1s Memory Limit: 128MB

这是一个经典的最短路问题，可以使用 Dijkstra 算法或者 Bellman-Ford 算法解决。以下是 Dijkstra 算法的示例代码：

import heapq

n, m, s, t = map(int, input().split())

# 构建邻接表
adj = [[] for _ in range(n + 1)]
for i in range(m):
    u, v, w = map(int, input().split())
    adj[u].append((v, w))
    adj[v].append((u, w))

# 初始化距离数组
dist = [float('inf')] * (n + 1)
dist[s] = 0

# 使用堆优化的 Dijkstra 算法求解最短路
pq = [(0, s)]
while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:
        continue
    for v, w in adj[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(pq, (dist[v], v))

print(dist[t])

时间复杂度为 O(m log n)，其中 m 为边数，n 为点数。