Overview

This problem asks us to find the shortest time to travel from the distribution center (point \(1\)) via a relay station (point \(K\)) to the final destination (point \(N\)).

Analysis

In this problem, simply “trying all possible routes” would result in an extremely large number of combinations, making it impractical. Also, since the graph has no negative costs, shortest path algorithms like Dijkstra’s algorithm are effective.

The key observation is that the shortest time for the route “point \(1\) → point \(K\) → point \(N\)” is equal to the sum of “the shortest distance from point \(1\) to point \(K\)” and “the shortest distance from point \(K\) to point \(N\)”.

In other words, by applying Dijkstra’s algorithm twice, we can find the overall shortest time.

If point \(K\) is unreachable from point \(1\), or point \(N\) is unreachable from point \(K\), then delivery is impossible and we output -1.

Algorithm

1. Build the graph in adjacency list format.
2. Use Dijkstra’s algorithm to compute the following two shortest distances:
   • Shortest distance from point \(1\) to each vertex (dist_from_1)
   • Shortest distance from point \(K\) to each vertex (dist_from_K)
3. The final answer is the value of dist_from_1[K] + dist_from_K[N].
4. If either distance is unreachable (distance is infinity), output -1.

Dijkstra’s algorithm uses a priority queue (heap) to efficiently extract the vertex with the minimum cost during the search.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  (Since Dijkstra’s algorithm is executed twice, each taking \(O((N + M) \log N)\))
• Space complexity: \(O(N + M)\)
  (Due to the adjacency list representation of the graph and the distance arrays)

Implementation Notes

• Since the graph is undirected, edges must be added in both directions from the input road information.

• In the initialization of Dijkstra’s algorithm, set the distance of the starting point to 0 and the distances of all other vertices to inf.

• Reachability can be determined by checking whether the result is inf, so it is safe to use float('inf') directly rather than a sufficiently large value for comparison.

  Source Code

import heapq
import sys

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

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    graph = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        c = int(data[idx]); idx += 1
        graph[u].append((v, c))
        graph[v].append((u, c))
    
    dist_from_1 = dijkstra(N, graph, 1)
    dist_from_K = dijkstra(N, graph, K)
    
    total_time = dist_from_1[K] + dist_from_K[N]
    if total_time >= float('inf'):
        print(-1)
    else:
        print(total_time)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.