概要

配送センター(地点1)から中継拠点(地点K)を経由して最終目的地(地点N)までの最短経路を求める問題です。

考察

この問題は、地点1→地点K→地点Nという経路を求める必要があります。素朴なアプローチとして、全地点間の最短経路を求めるワーシャルフロイド法が考えられますが、Nが最大200,000と大きいため、O(N³)の計算量では実行不可能です。

重要な観察は、経路が「地点1→地点K」と「地点K→地点N」の2つの部分に分解できることです。それぞれの部分の最短経路を個別に求め、それらを足し合わせることで全体の最短経路が得られます。

アルゴリズム

ダイクストラ法を3回適用します： 1. 地点1を始点として、全地点への最短距離を計算 2. 地点Kを始点として、全地点への最短距離を計算
3. 地点Nを始点として、全地点への最短距離を計算（実装では不要ですが、地点K→地点Nの距離を得るために地点Kを始点とするダイクストラで十分）

実際の実装では、以下のように計算します： - dist1[k]：地点1→地点Kの最短距離 - distK[n]：地点K→地点Nの最短距離 - 合計 dist1[k] + distK[n] が求める答え

もしどちらかの経路が存在しない場合（距離が無限大の場合）は、全体の経路も存在しないため-1を出力します。

計算量

• 時間計算量: \(O((N + M) \log N)\)（ダイクストラ法を2回実行）
• 空間計算量: \(O(N + M)\)（グラフの表現と距離配列のため）

実装のポイント

• ダイクストラ法の実装では、ヒープを使用して効率的に最短距離を更新します

• 距離の初期値は十分大きな値（10¹⁸）に設定し、到達不能を判定します

• グラフは隣接リスト形式で表現し、メモリ使用量を抑えます

• 各道路は双方向なので、両方向に辺を追加します

  ソースコード

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()

この解説は deepseekv3 によって生成されました。