概要

グラフ上の複数のチェックポイントを指定された順番通りに通過し、スタートからゴールまで移動する際の最小合計時間を求める問題です。

考察

この問題の最も重要な点は、「チェックポイントを訪れる順番が \(P_1, P_2, \ldots, P_K\) とあらかじめ決まっている」ことです。

もし訪問順が自由であれば「巡回セールスマン問題」と呼ばれる難解な問題になりますが、順番が決まっているため、この問題は以下の区間ごとの最短距離を求める問題に分解できます。

1. スタート（地点 \(1\)）から \(P_1\) までの最短距離
2. \(P_1\) から \(P_2\) までの最短距離
3. …
4. \(P_{K-1}\) から \(P_K\) までの最短距離
5. \(P_K\) からゴール（地点 \(N\)）までの最短距離

全体の最小移動時間は、これらの各区間の最短距離をすべて足し合わせたものになります。

各区間の最短距離を求めるには、負の辺がないためダイクストラ法が適しています。制約を確認すると、チェックポイントの数 \(K\) は最大 \(10\) と非常に小さいため、ダイクストラ法を最大 \(K+1\) 回（各出発地点から 1 回ずつ）実行しても実行時間制限に十分間に合います。

アルゴリズム

以下の手順で解を求めます。

1. グラフの構築: 与えられた \(M\) 本の道を隣接リスト形式で保持します。
2. 訪問ルートの整理: 訪問する順番を [1, P_1, P_2, ..., P_K, N] というリストにまとめます。
3. 最短距離の計算:
   • リストに含まれる各地点（終点の \(N\) を除く）を起点として、ダイクストラ法を実行します。
   • 同じ地点が複数回登場する場合に備え、計算結果をメモ（キャッシュ）しておくと効率的です。
4. 合計時間の算出:
   • 各区間 \((path_i, path_{i+1})\) の最短距離を足していきます。
   • もし途中で到達不可能な地点（距離が無限大）があれば、その時点で -1 を出力して終了します。
5. 結果の出力: 全区間を合計した値を最小移動時間として出力します。

計算量

• 時間計算量: \(O(K \cdot M \log N)\)
  • ダイクストラ法 1 回あたりの計算量は \(O(M \log N)\) です。
  • これを最大 \(K+1\) 回繰り返すため、全体では \(O(K \cdot M \log N)\) となります。
  • \(K \le 10, M = 10^5, N = 5 \times 10^4\) であるため、およそ \(1.7 \times 10^7\) 回程度の操作となり、制限時間内に収まります。
• 空間計算量: \(O(N + M)\)
  • 隣接リストの保存に \(O(N + M)\)、ダイクストラ法の距離配列に \(O(N)\) のメモリを使用します。

実装のポイント

• ダイクストラ法の共通化: 起点を引数にとる関数として実装することで、コードの重複を避けます。

• 到達不能判定: 初期値を非常に大きな値（INF）に設定し、ダイクストラ法実行後も値が INF のままであれば、その地点には到達できないと判断します。

• 高速な入出力: \(N\) や \(M\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

  ソースコード

import sys
import heapq

def solve():
    # Read all input at once for faster processing
    try:
        raw_data = sys.stdin.read()
        if not raw_data:
            return
        input_data = raw_data.split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # Parse N (checkpoints), M (roads), and K (checkpoints to visit)
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # Build the graph as an adjacency list
    # adj[u] stores a list of (neighbor, travel_time) tuples
    adj = [[] for _ in range(N + 1)]
    ptr = 3
    for _ in range(M):
        u = int(input_data[ptr])
        v = int(input_data[ptr+1])
        t = int(input_data[ptr+2])
        adj[u].append((v, t))
        adj[v].append((u, t))
        ptr += 3
        
    # The K checkpoints to be visited in the given order
    P = list(map(int, input_data[ptr:ptr+K]))
    
    # The full sequence of nodes to visit: Start at 1 -> P1 -> P2 -> ... -> PK -> End at N
    path = [1] + P + [N]
    
    # We only need to run Dijkstra's algorithm from each unique starting point in the path.
    # The last node N is only a destination (unless it is also one of the specified checkpoints).
    unique_starts = set(path[:-1])
    
    # Cache to store shortest path distances from each unique starting node
    memo = {}
    INF = 10**18  # A sufficiently large value for infinity
    
    # Localize heapq functions for faster lookup in the Dijkstra loop
    push = heapq.heappush
    pop = heapq.heappop
    
    # Implementation of Dijkstra's algorithm
    def run_dijkstra(start_node):
        distances = [INF] * (N + 1)
        distances[start_node] = 0
        pq = [(0, start_node)]
        
        while pq:
            d, u = pop(pq)
            
            # If a shorter path to node u has already been found, skip this entry
            if d > distances[u]:
                continue
            
            # Relax all edges connected to node u
            for v, weight in adj[u]:
                new_dist = d + weight
                if new_dist < distances[v]:
                    distances[v] = new_dist
                    push(pq, (new_dist, v))
        return distances

    # Pre-calculate Dijkstra results for all required starting nodes
    for u in unique_starts:
        memo[u] = run_dijkstra(u)
        
    total_time = 0
    # Sum the shortest distances for each consecutive segment of the required path
    for i in range(len(path) - 1):
        u = path[i]
        v = path[i+1]
        
        # Retrieve the shortest distance from u to v from the memoized results
        d_uv = memo[u][v]
        
        # If any part of the journey is impossible, output -1
        if d_uv >= INF:
            print("-1")
            return
        
        total_time += d_uv
        
    # Output the minimum total travel time required to complete the rally
    print(total_time)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。