概要

本問題は、与えられた重み付き無向グラフにおいて、スタート（地点 \(1\)）からゴール（地点 \(N\)）までの所要時間が \(T\) 以下となる経路のうち、経路上で訪れる頂点の「危険度」の最大値を最小化する問題です。

考察

単純なアプローチの難しさ

「最短経路を求めつつ、危険度も最小化する」という2つの目的を同時に達成しようとすると、状態の持たせ方が複雑になります。例えば、各頂点に対して「その頂点に危険度 \(x\) 以下で到達するときの最短時間」を管理するような動的計画法（DP）を考えると、危険度の値が最大で \(10^9\) と非常に大きいため、メモリや実行時間が足りなくなってしまいます。

重要な気づき：単調性と二分探索

ここで、問題を逆転させて考えてみましょう。 「経由する頂点の危険度を \(X\) 以下に制限したとき、時間 \(T\) 以内にゴールできるか？」という判定問題を考えます。

この判定問題には、以下の単調性が成り立ちます。 - 許容する危険度 \(X\) が大きくなればなるほど、通れる頂点が増えるため、ゴールに時間 \(T\) 以内に到達しやすくなる。 - 逆に、危険度 \(X\) が小さすぎると、通れる頂点が制限されてゴールに到達できなくなる。

このように「ある値 \(X\) 以上なら条件を満たし、\(X\) 未満なら満たさない」という境界が存在する場合、二分探索（Binary Search）を用いて最適な \(X\) を効率よく見つけることができます。

判定問題の解き方（ダイクストラ法）

危険度 \(X\) を固定したとき、危険度が \(X\) より大きい頂点は一切通ることができません。 したがって、「危険度が \(X\) 以下の頂点のみからなる部分グラフ」において、地点 \(1\) から地点 \(N\) への最短経路を求め、その所要時間が \(T\) 以下であるかを判定すればよいです。これは、ダイクストラ法を用いて \(O(M \log N)\) で解くことができます。

---

アルゴリズム

1. 危険度の候補の洗い出し

   • 経由する可能性のある危険度の値は、与えられた頂点の危険度 \(P_i\) のいずれかです。
   • ただし、スタート地点 \(1\) とゴール地点 \(N\) は必ず通るため、経路の危険度の最小値は \(\max(P_1, P_N)\) 以上になります。
   • したがって、\(P\) の中から \(\max(P_1, P_N)\) 以上のユニークな値を抽出し、昇順にソートした配列 \(A\) を作成します。この \(A\) の要素が二分探索の探索対象（危険度 \(X\) の候補）となります。

2. 二分探索の実行

   • 探索範囲の左端を low = 0、右端を high = len(A) - 1 とします。
   • mid = (low + high) // 2 とし、危険度 \(X = A[mid]\) として判定関数 check(X) を呼び出します。
     • check(X) が True の場合: 危険度 \(X\) で到達可能なので、さらに小さい危険度で到達できるか調べるため、high = mid - 1 とし、暫定の答えを更新します。
     • check(X) が False の場合: 危険度 \(X\) では到達不可能なので、より大きな危険度を許容する必要があり、low = mid + 1 とします。

3. 判定関数 check(X) の詳細

   • スタート地点 \(1\) からの最短距離を保持する配列 dist を、十分大きな値（\(T + 1\) など）で初期化します。
   • 優先度付きキュー（ヒープ）を用いて、ダイクストラ法を実行します。
   • 遷移先の頂点 \(v\) の危険度が \(P_v \leq X\) を満たす場合のみ、最短距離の更新とキューへの追加を行います。
   • ゴール地点 \(N\) に到達した時点で探索を終了し、True を返します。キューが空になってもゴールに到達できなければ False を返します。

---

計算量

• 時間計算量: \(O(M \log N \log N)\)

  • 危険度のユニークな値の数を \(U\) とします（\(U \leq N\)）。二分探索のステップ数は \(O(\log U)\) 回です。
  • 各ステップで実行するダイクストラ法の時間計算量は \(O(M \log N)\) です。
  • 全体の時間計算量は \(O(M \log N \log U) \subseteq O(M \log^2 N)\) となり、制約下（\(N \le 2 \times 10^4, M \le 4 \times 10^4\)）において実行時間制限に十分間に合います。

• 空間計算量: \(O(N + M)\)

  • グラフを表現する隣接リスト adj に \(O(N + M)\)、最短距離配列 dist や優先度付きキューに \(O(N)\) のメモリを使用します。

---

実装のポイント

• 探索範囲の削減: スタートとゴールの危険度 \(\max(P_1, P_N)\) 未満の危険度を二分探索の候補からあらかじめ除外しておくことで、二分探索の回数を減らし、ダイクストラ法での無駄な探索を省くことができます。

• 高速な入出力: Pythonにおいて入力行数が多い場合は、sys.stdin.read().split() を用いて一括で入力を取得することで、入出力によるボトルネックを解消できます。

  ソースコード

import heapq
import sys


def solve():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    T = int(input_data[2])

    P = [int(x) for x in input_data[3 : 3 + N]]

    adj = [[] for _ in range(N)]
    idx = 3 + N
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx + 1]) - 1
        w = int(input_data[idx + 2])
        adj[u].append((v, w))
        adj[v].append((u, w))
        idx += 3

    # 起点と終点の危険度の最大値が、探索する危険度の下限となる
    P_start_end = max(P[0], P[N - 1])
    P_unique = sorted(list(set(P)))
    A = [x for x in P_unique if x >= P_start_end]

    # 危険度 X 以下の頂点のみを用いて、時間 T 以内にゴールできるか判定
    def check(X):
        dist = [T + 1] * N
        dist[0] = 0
        pq = [(0, 0)]  # (d, u)
        while pq:
            d, u = heapq.heappop(pq)
            if u == N - 1:
                return True
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                if P[v] <= X:
                    nd = d + w
                    if nd < dist[v]:
                        dist[v] = nd
                        heapq.heappush(pq, (nd, v))
        return False

    # 二分探索
    low = 0
    high = len(A) - 1
    ans = A[high]

    while low <= high:
        mid = (low + high) // 2
        if check(A[mid]):
            ans = A[mid]
            high = mid - 1
        else:
            low = mid + 1

    print(ans)


if __name__ == "__main__":
    solve()

---

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