Overview

Starting from point \(1\), we find the shortest time to reach point \(N\) while necessarily passing through point \(K\), formulated as a shortest path problem on a weighted undirected graph.

Analysis

The key point of this problem is the condition “must pass through \(K\).” Simply finding the shortest path from \(1 \to N\) does not guarantee that the path passes through \(K\).

The important observation is as follows:

• Any path from \(1\) to \(N\) that passes through \(K\) along the way can be split into a “\(1 \to K\) portion” and a “\(K \to N\) portion.”
• Therefore, the answer is $\( \text{dist}(1,K) + \text{dist}(K,N) \)$ (if we take the shortest path for each portion, the overall path is also shortest).

A naive approach like “try all shortest paths from \(1\) and select only those passing through \(K\)” is impractical due to the enormous number of possible paths. Also, since \(N,M \le 2\times 10^5\), solutions that compute shortest distances from each vertex multiple times will not be fast enough.

Instead, we: - Run Dijkstra’s algorithm from \(1\) as the source to obtain shortest distances to all vertices, giving us \(\text{dist}(1, \cdot)\) - Run Dijkstra’s algorithm again from \(K\) as the source to obtain shortest distances to all vertices, giving us \(\text{dist}(K, \cdot)\)

This immediately gives us the needed \(\text{dist}(1,K)\) and \(\text{dist}(K,N)\). If either is unreachable, then \(1 \to K \to N\) is naturally impossible, so we output -1.

Algorithm

1. Build an undirected graph using an adjacency list (add each road \((u,v,c)\) in both directions).
2. Run Dijkstra’s algorithm twice.
   • 1st run: Obtain the shortest distance array dist1 from source \(1\).
   • 2nd run: Obtain the shortest distance array distK from source \(K\).
3. If dist1[K] or distK[N] is INF (unreachable), output -1.
4. Otherwise, output dist1[K] + distK[N].

The reason for using Dijkstra’s algorithm is that all travel times \(C_i\) are positive (\(C_i \ge 1\)), making it efficient for computing weighted shortest paths.

Complexity

• Time complexity: \(O((N+M)\log N)\) run twice, so \(O((N+M)\log N)\)
• Space complexity: \(O(N+M)\) for the adjacency list and distance arrays

Implementation Notes

• Make INF sufficiently large: Distances can potentially be the sum of many values up to \(10^9\), so use a large value like 10**30.

• Discard “stale information” from the priority queue: By including if d != dist[v]: continue, we ignore elements extracted with outdated distances, preserving the time complexity.

• Add edges in both directions since the graph is undirected: Don’t forget to add both graph[u].append((v,c)) and graph[v].append((u,c)).

  Source Code

import sys
import heapq

def dijkstra(start, graph, n):
    INF = 10**30
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, v = heapq.heappop(pq)
        if d != dist[v]:
            continue
        for to, w in graph[v]:
            nd = d + w
            if nd < dist[to]:
                dist[to] = nd
                heapq.heappush(pq, (nd, to))
    return dist

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, c = map(int, input().split())
        graph[u].append((v, c))
        graph[v].append((u, c))

    dist1 = dijkstra(1, graph, N)
    distK = dijkstra(K, graph, N)

    INF = 10**30
    if dist1[K] >= INF or distK[N] >= INF:
        print(-1)
    else:
        print(dist1[K] + distK[N])

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.