Overview

This is a problem of finding the minimum time to travel from starting point \(S\), via point \(G\) where a package is located, to destination \(T\). This problem can be reduced to the “shortest path problem” on a graph.

Analysis

Takahashi’s movement can be divided into the following two phases: 1. Moving from point \(S\) to point \(G\) (going to pick up the package) 2. Moving from point \(G\) to point \(T\) (delivering the package)

The total travel time is the sum of the times for each phase. To find the minimum time, we need to compute the “shortest distance from \(S\) to \(G\)” and the “shortest distance from \(G\) to \(T\)”.

Here, we note that the roads are bidirectional (undirected graph). In an undirected graph, the shortest distance from \(S\) to \(G\) is equal to the shortest distance from \(G\) to \(S\). Therefore, by running Dijkstra’s algorithm just once with point \(G\) as the source, we can simultaneously obtain the distances to both point \(S\) and point \(T\), which is very efficient.

If no path exists from \(G\) to \(S\) or from \(G\) to \(T\) (i.e., the distance remains infinity), then the required movement is impossible, so we output \(-1\).

Algorithm

This problem is solved using Dijkstra’s algorithm, which solves the single-source shortest path problem on graphs with non-negative edge weights.

1. Create an adjacency list for points \(1\) through \(N\) and store the information for each road.
2. Run Dijkstra’s algorithm starting from point \(G\).
   • Prepare a priority queue (heapq) and add (cost 0, point G).
   • Initialize the array dist that holds the shortest distance to each point with infinity (inf), and set dist[G] = 0.
   • Repeat the process of extracting the point with the minimum cost from the queue and updating the scores of adjacent points.
3. Check the computed dist[S] and dist[T].
   • If either is inf, output \(-1\).
   • Otherwise, output dist[S] + dist[T].

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • This is because Dijkstra’s algorithm involves edge relaxation and priority queue operations. Under the constraints \(N=10^5, M=1.5 \times 10^5\), this complexity is well within the time limit.
• Space complexity: \(O(N + M)\)
  • Memory is needed for the adjacency list to store the graph and the array to store distances.

Implementation Notes

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

• Priority queue: Python’s heapq module provides a min-heap, making it straightforward to implement Dijkstra’s algorithm.

• Unreachability detection: Initialize the shortest distance array with a sufficiently large value (such as float('inf')), and if the final value remains unchanged, determine it as “unreachable”.

  Source Code

import heapq
import sys

def solve():
    # 入力を一度に読み込み、高速化を図る
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 地点数, M: 道路数, S: スタート地点, G: 荷物地点, T: ゴール地点
    N = int(input_data[0])
    M = int(input_data[1])
    S = int(input_data[2])
    G = int(input_data[3])
    T = int(input_data[4])
    
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    ptr = 5
    for _ in range(M):
        u = int(input_data[ptr])
        v = int(input_data[ptr+1])
        c = int(input_data[ptr+2])
        adj[u].append((v, c))
        adj[v].append((u, c))
        ptr += 3
        
    # ダイクストラ法
    # 地点 G から全地点への最短距離を求めることで、dist(S, G) と dist(G, T) を一度に得る
    def dijkstra(start_node):
        distances = [float('inf')] * (N + 1)
        distances[start_node] = 0
        pq = [(0, start_node)] # (コスト, 現在の地点)
        
        while pq:
            current_dist, u = heapq.heappop(pq)
            
            # すでに確定している最短経路より長い場合はスキップ
            if current_dist > distances[u]:
                continue
            
            for v, weight in adj[u]:
                distance = current_dist + weight
                
                # より短い経路が見つかった場合、更新してキューに追加
                if distance < distances[v]:
                    distances[v] = distance
                    heapq.heappush(pq, (distance, v))
        return distances

    # 地点 G からの最短距離を計算
    dist_from_g = dijkstra(G)
    
    # S から G への距離と G から T への距離を取得
    # 無向グラフのため dist(S, G) == dist(G, S)
    d_gs = dist_from_g[S]
    d_gt = dist_from_g[T]
    
    # 到達可能か判定し、結果を出力
    if d_gs == float('inf') or d_gt == float('inf'):
        print("-1")
    else:
        # 必要な最小時間は dist(S, G) + dist(G, T)
        print(d_gs + d_gt)

if __name__ == "__main__":
    solve()

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