Submission #73633683

---

Source Code Expand

from heapq import heappop, heappush

N, M, T = [*map(int, input().split())]
T -= 1

edges = [tuple(map(int, input().split())) for _ in range(M)]
edges = [(A - 1, B - 1, C) for A, B, C in edges]

adj = [[] for _ in range(N)]
for u, v, w in edges:
    adj[u].append((v, w))
    adj[v].append((u, w))

INF = 10**20


def dijk(s: int) -> list[int]:
    dis = [INF] * N
    vis = [False] * N
    pq = []

    dis[s] = 0
    heappush(pq, (0, s))

    while pq:
        d, u = heappop(pq)

        if vis[u]:
            continue

        vis[u] = True

        for v, w in adj[u]:
            if not vis[v] and dis[v] > d + w:
                dis[v] = d + w
                heappush(pq, (dis[v], v))

    return dis


dis = dijk(0)

if dis[T] != INF:
    print(2 * dis[T])
else:
    print(-1)

Submission Info

Judge Result