soulution.py

import heapq

def dijkstra(graph, start, end):
    # 距离数组，初始化为无穷大
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    # 优先队列，存储节点和到起点的距离
    pq = [(0, start)]

    while pq:
        # 取出距离起点最近的节点
        distance, node = heapq.heappop(pq)
        # 如果该节点已经被处理过，则跳过
        if distance > dist[node]:
            continue
        # 更新该节点的所有邻居节点的距离值
        for neighbor, weight in graph[node].items():
            new_dist = dist[node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    # 返回从起点到终点的最短距离
    return dist[end] if dist[end] < float('inf') else "INF"

# 读入有向加权图和起点、终点
n, m, s = map(int, input().split())
graph = {i: {} for i in range(1, n+1)}
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u][v] = w

# 计算从起点到终点的最短距离
print(dijkstra(graph, s, n))