import heapq

def min_delay(N, M, times, src, dst):
    # 构建邻接表
    graph = [[] for _ in range(N + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    
    # 初始化距离数组
    dist = [float('inf')] * (N + 1)
    dist[src] = 0
    
    # 使用优先队列（最小堆）
    heap = [(0, src)]
    
    while heap:
        current_dist, u = heapq.heappop(heap)
        if u == dst:
            return current_dist
        if current_dist > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    return -1

# 读取输入
N, M = map(int, input().split())
times = []
for _ in range(M):
    u, v, w = map(int, input().split())
    times.append((u, v, w))
src, dst = map(int, input().split())

# 计算并输出结果
result = min_delay(N, M, times, src, dst)
print(result)

解决思路

这是一个典型的单源最短路径问题，可以使用以下算法：

1. Dijkstra算法：适用于非负权边的图，时间复杂度为O(M + N log N)。
2. Bellman-Ford算法：适用于一般情况（包括负权边，但本题无负权边），时间复杂度为O(N*M)。
3. SPFA算法：Bellman-Ford的优化版本，平均时间复杂度为O(M)，最坏情况下为O(N*M)。

由于题目中时延为非负数（0 ≤ w ≤ 100），Dijkstra算法是最优选择。