Overview

This problem asks us to find the shortest time to travel from point \(1\) to point \(N\) via point \(K\). We need to efficiently compute the shortest path through a specific intermediate point in a weighted undirected graph.

Analysis

We can decompose the route to the destination into the following two segments: 1. The shortest path from point \(1\) to point \(K\) 2. The shortest path from point \(K\) to point \(N\)

The sum of the shortest times for these two segments gives the overall shortest time.

Since each road has a weight called “travel time,” it is appropriate to use Dijkstra’s algorithm rather than a simple breadth-first search (BFS).

Normally, we might consider running Dijkstra’s algorithm twice — once from point \(1\) and once from point \(K\). However, the graph in this problem is an “undirected graph (traversable in both directions).” In an undirected graph, “the distance from point \(1\) to \(K\)” equals “the distance from point \(K\) to \(1\).” Therefore, by running Dijkstra’s algorithm just once with the intermediate point \(K\) as the starting point, we can simultaneously obtain the shortest distance to point \(1\) and the shortest distance to point \(N\), which is very efficient.

Algorithm

1. Graph Construction: Store the given road information in adjacency list format.
2. Running Dijkstra’s Algorithm:
   • Set point \(K\) as the starting point and initialize the array dist, which stores the shortest distance to each point, with infinity (inf) (with dist[k] = 0).
   • Use a priority queue (heap) to explore points in order of increasing distance among unfinalized points.
3. Result Determination:
   • Check the distance from point \(K\) to point \(1\), dist[1], and the distance from point \(K\) to point \(N\), dist[n].
   • If either remains at the initial value (inf), determine that the destination is unreachable and output -1.
   • If both are reachable, output their sum dist[1] + dist[n].

Complexity

• Time Complexity: \(O(M \log N)\)
  • The complexity of Dijkstra’s algorithm is \(O(M \log N)\), where \(N\) is the number of points and \(M\) is the number of roads (edges). Under the given constraints (\(N, M \leq 2 \times 10^5\)), this comfortably fits within the time limit.
• Space Complexity: \(O(N + M)\)
  • \(O(N + M)\) memory is used for storing the adjacency list, and \(O(N)\) for the shortest distance array.

Implementation Notes

• Fast I/O: Since \(N, M\) can be large, in Python, reading all input at once using sys.stdin.read().split() can reduce execution time.

• Priority Queue: By using the heapq module, Dijkstra’s algorithm can be implemented efficiently.

• Unreachability Check: If either of the two segments is unreachable, the overall route is infeasible, so each segment must be checked individually.

  Source Code

import sys
import heapq

def solve():
    # 入力を一括で読み込み、イテレータに変換して高速化
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    n = int(next(it))
    m = int(next(it))
    k = int(next(it))

    # 隣接リストの構築
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        c = int(next(it))
        adj[u].append((v, c))
        adj[v].append((u, c))

    # 地点 K から他の全地点への最短距離をダイクストラ法で求める
    # 地点 1 から K を経由して N へ行く最短時間は、dist(1, K) + dist(K, N) となる。
    # 無向グラフなので dist(1, K) = dist(K, 1) であり、K を始点とするダイクストラ1回で済む。
    inf = float('inf')
    dist = [inf] * (n + 1)
    dist[k] = 0
    pq = [(0, k)]

    while pq:
        d, u = heapq.heappop(pq)
        
        # すでに確定している距離より大きい場合はスキップ
        if d > dist[u]:
            continue
            
        for v, cost in adj[u]:
            new_dist = d + cost
            if dist[v] > new_dist:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    
    # Kから地点1までの距離と、Kから地点Nまでの距離を取得
    dist_k_to_1 = dist[1]
    dist_k_to_n = dist[n]
    
    # どちらかが到達不可能な場合は -1 を出力
    if dist_k_to_1 == inf or dist_k_to_n == inf:
        print("-1")
    else:
        # 1 -> K -> N の合計時間を計算して出力
        print(dist_k_to_1 + dist_k_to_n)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.