1129. 热浪.py

import collections
import heapq
def ipt_helper(): return map(int, input().split())


N, M, D = int(1e5 + 5), int(1e5 + 5), float('inf')
dist, vt = [D] * N, [False] * N

h, e, ne, edges, idx = [0] * N, [0] * M, [0] * M, [0] * M, 0

n, m, st, ed = ipt_helper()


def add(u, v, z):
    global idx
    idx += 1
    e[idx], ne[idx], h[u], edges[idx] = v, h[u], idx, z


def heapify_dijkstra():
    pq, dist[st] = [], 0
    heapq.heappush(pq, (0, st))
    while pq:
        d, u = heapq.heappop(pq)
        if vt[u]:
            continue
        vt[u] = True
        u = h[u]
        while u:
            v, u_v_edge = e[u], edges[u]
            if dist[v] > d + u_v_edge:
                dist[v] = d + u_v_edge
                heapq.heappush(pq, (dist[v], v))
            u = ne[u]
    return dist[ed]


def spfa():
    que = collections.deque([1])
    dist[st] = 0
    vt[st] = True

    while que:
        u_idx = que.popleft()
        vt[u_idx] = False
        u = h[u_idx]
        while u:
            v = e[u]
            if dist[v] > dist[u] + edges[u]:
                dist[v] = dist[u] + edges[u]
                if v in vt:
                    continue
                que.append(v)
                vt[v] = True
            u = ne[u]

    return dist[ed]


for _ in range(m):
    u, v, z = ipt_helper()
    add(u, v, z)
    add(v, u, z)

# dist_n = spfa()
dist_n = heapify_dijkstra()
print(-1 if dist_n == D else dist_n)