Overview

This is a problem of finding the shortest path from point \(1\) to point \(N\) via relay point \(K\). It can be solved efficiently by running Dijkstra’s algorithm twice.

Analysis

Key Insight: Decomposing a Shortest Path with a Waypoint

The shortest path with a waypoint “point \(1\) → point \(K\) → point \(N\)” can be decomposed into the following two parts:

1. Shortest distance from point \(1\) to point \(K\): \(d(1, K)\)
2. Shortest distance from point \(K\) to point \(N\): \(d(K, N)\)

The answer is \(d(1, K) + d(K, N)\).

This works because, due to the constraint that we must pass through waypoint \(K\), we can “split” the path at \(K\). Even if we independently find the shortest path from \(1 \to K\) and the shortest path from \(K \to N\), the overall shortest time remains the same.

Issues with a Naive Approach

If we try to compute shortest distances between all pairs of vertices, the Floyd-Warshall algorithm takes \(O(N^3)\), which is far too slow for this problem where \(N\) can be up to \(2 \times 10^5\).

Solution

We only need two things: “shortest distances from point \(1\) as the source” and “shortest distances from point \(K\) as the source.” Running Dijkstra’s algorithm twice is sufficient.

• 1st run: Shortest distance array from source \(1\) → gives us \(d(1, K)\)
• 2nd run: Shortest distance array from source \(K\) → gives us \(d(K, N)\)

Algorithm

1. Build the graph using an adjacency list.
2. Dijkstra’s algorithm (1st run): Starting from point \(1\), compute the shortest distances to all vertices. Extract \(d(1, K)\) from this.
3. Dijkstra’s algorithm (2nd run): Starting from point \(K\), compute the shortest distances to all vertices. Extract \(d(K, N)\) from this.
4. If \(d(1, K)\) or \(d(K, N)\) is \(\infty\) (unreachable), output -1. Otherwise, output \(d(1, K) + d(K, N)\).

Concrete Example

For example, suppose \(N=4, K=3\) with the following roads:

• \(1 \leftrightarrow 2\) (cost \(2\))
• \(2 \leftrightarrow 3\) (cost \(3\))
• \(3 \leftrightarrow 4\) (cost \(1\))

Then: - \(d(1, 3) = 2 + 3 = 5\) (\(1 \to 2 \to 3\)) - \(d(3, 4) = 1\) (\(3 \to 4\)) - Answer: \(5 + 1 = 6\)

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Each run of Dijkstra’s algorithm takes \(O((N + M) \log N)\), and we run it twice.
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) for the adjacency list of the graph, and \(O(N)\) for the distance arrays.

Implementation Notes

• Fast input: Since \(N, M\) can be as large as \(2 \times 10^5\), we read all input at once using sys.stdin.buffer.read(), then split and process it, allowing sufficient speed even in Python.

• Initial distance values: By using float('inf'), we can concisely determine whether a vertex is unreachable.

• Overflow considerations: Edge costs can be up to \(10^9\), and path lengths can reach approximately \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\), but since Python has no integer overflow, this is not a concern.

• Pruning with d > dist[u]: When the distance extracted from the priority queue is already larger than the currently known shortest distance, we skip it to avoid unnecessary exploration.

  Source Code

import heapq
import sys

def dijkstra(graph, start, n):
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        graph[u].append((v, c))
        graph[v].append((u, c))
    
    dist_from_1 = dijkstra(graph, 1, N)
    dist_from_k = dijkstra(graph, K, N)
    
    INF = float('inf')
    d1k = dist_from_1[K]
    dkn = dist_from_k[N]
    
    if d1k == INF or dkn == INF:
        print(-1)
    else:
        print(d1k + dkn)

main()

---

This editorial was generated by claude4.6opus-thinking.