Overview

This is a problem of finding the shortest path from a distribution center (point 1) through a relay station (point K) to the final destination (point N).

Analysis

This problem requires finding a route from point 1 → point K → point N. A naive approach would be the Floyd-Warshall algorithm, which computes shortest paths between all pairs of points. However, since N can be as large as 200,000, the O(N³) time complexity makes this infeasible.

The key observation is that the route can be decomposed into two parts: “point 1 → point K” and “point K → point N.” By computing the shortest path for each part individually and summing them, we obtain the overall shortest path.

Algorithm

We apply Dijkstra’s algorithm twice (or three times): 1. Compute the shortest distances from point 1 to all other points 2. Compute the shortest distances from point K to all other points 3. Compute the shortest distances from point N to all other points (in practice this is unnecessary, since running Dijkstra from point K is sufficient to obtain the distance from point K to point N)

In the actual implementation, we compute: - dist1[k]: the shortest distance from point 1 → point K - distK[n]: the shortest distance from point K → point N - The answer is dist1[k] + distK[n]

If either route does not exist (i.e., the distance is infinity), then the overall route does not exist either, so we output -1.

Complexity

• Time complexity: \(O((N + M) \log N)\) (running Dijkstra’s algorithm twice)
• Space complexity: \(O(N + M)\) (for the graph representation and distance arrays)

Implementation Notes

• The Dijkstra implementation uses a heap (priority queue) to efficiently update shortest distances

• Initial distance values are set to a sufficiently large value (10¹⁸) to detect unreachable points

• The graph is represented as an adjacency list to reduce memory usage

• Since each road is bidirectional, edges are added in both directions

  Source Code

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it)); k = int(next(it))
    
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        u = int(next(it)); v = int(next(it)); c = int(next(it))
        graph[u].append((v, c))
        graph[v].append((u, c))
    
    def dijkstra(start):
        dist = [10**18] * (n+1)
        dist[start] = 0
        heap = [(0, start)]
        
        while heap:
            d, node = heapq.heappop(heap)
            if d != dist[node]:
                continue
            for neighbor, cost in graph[node]:
                new_d = d + cost
                if new_d < dist[neighbor]:
                    dist[neighbor] = new_d
                    heapq.heappush(heap, (new_d, neighbor))
        return dist
    
    dist1 = dijkstra(1)
    distK = dijkstra(k)
    distN = dijkstra(n)
    
    if dist1[k] == 10**18 or distK[n] == 10**18:
        print(-1)
    else:
        print(dist1[k] + distK[n])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.