task3.py

# s = 0, t = 1

# O(ElogV)

from checker import check
from heapq import heappop, heappush
inf = float('inf')

def edges_to_list(E):
    n = 0

    for u, v, _ in E:
        u -= 1 # korekcja indeksowania od 1
        v -= 1
        if u > n: n = u
        if v > n: n = v

    n += 1

    G = [[] for _ in range(n)]

    for u, v, w in E:
        u -= 1
        v -= 1
        G[u].append((v, w))
        G[v].append((u, w))

    return G, n

def maxheappush(PQ, w, v):
    heappush(PQ, (-w, v))

def maxheappop(PQ):
    w, v = heappop(PQ)
    return -w, v

def dijkstra(G, s, t, n):
    d = [-inf for _ in range(n)]

    PQ = [(inf, s)]
    d[s] = inf

    while len(PQ) > 0:
        u_w, u = maxheappop(PQ)

        if u == t: break
        if u != s and d[u] > u_w: continue

        for v, w in G[u]:
            c = d[u] if d[u] < w else w
            if d[v] < c:
                d[v] = c
                maxheappush(PQ, c, v)
    
    return d[t]

def solution(E):
    s, t = 0, 1
    G, n = edges_to_list(E)

    return dijkstra(G, s, t, n)

check(solution)