概要

地点 \(1\) から地点 \(N\) まで所要時間が \(T\) 以下で到達できる経路の中で、経路上の地点の危険度の最大値を最小化する問題です。

考察

この問題は、「危険度の最大値を最小化する」という典型的な最適化問題です。このような問題では、二分探索を用いて「危険度の最大値が \(X\) 以下となる経路が存在するか？」という判定問題に帰着させるのが有効です。

素朴な考え方として、すべての経路を列挙してその中から条件を満たすものを探すことも考えられますが、経路の数は膨大になるため間に合いません。

二分探索を用いる場合、ある閾値 \(X\) を設定し、「危険度が \(X\) 以下の地点のみを通って地点 \(1\) から地点 \(N\) まで時間 \(T\) 以内に到達できるか」を判定できればよいことになります。この判定問題は、\(X\) 以下の危険度を持つ頂点のみを用いたグラフに対して、最短時間を求めることで解くことができます。時間の最小化なのでダイクストラ法を利用します。

アルゴリズム

1. 二分探索の準備: 危険度の候補となる値は、各地点の危険度 \(P_i\) のいずれかです。したがって、\(P\) の要素をソートし、重複を取り除いたリスト vals を作成します。このリストに対して二分探索を行います。 なお、出発地点と到着地点は必ず経路に含まれるため、探索の下限を max(P[0], P[N-1]) に設定すると計算量を少し削減できます。

2. 判定関数 check(X): 危険度の上限を \(X\) としたとき、時間 \(T\) 以内に到達可能かを判定します。

   • もし地点 \(N\) 自体の危険度が \(X\) を超えている場合、明らかに到達不可なので False を返します。
   • それ以外の場合、ダイクストラ法を用いて地点 \(1\) からの最短時間を求めます。このとき、遷移先として選べる頂点 \(v\) は「危険度が \(X\) 以下であること（\(P_v \leq X\)）」を条件とします。
   • 計算の途中で時間が \(T\) を超える経路は探索する必要がないため、距離の配列 dist の初期値を \(T+1\) とし、新たな距離 nd が \(T\) 以下の場合のみ優先度付きキューに追加します。
   • 最終的に地点 \(N\) までの到達時間が \(T\) 以下であれば True、そうでなければ False を返します。

3. 二分探索の実行: check(X) が True となる最小の \(X\) を二分探索で見つけ出し、出力します。

計算量

• 時間計算量: \(O(M \log N \log N)\)
  • ダイクストラ法が \(O(M \log N)\)、二分探索が \(O(\log N)\) 回（\(N\) は地点数ですが、\(P\) の種類数は最大 \(N\) であるため）。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストと距離配列を保持するため。

実装のポイント

• Pythonでの入力速度を上げるため、sys.stdin.readline を使用します。

• 二分探索の探索範囲（下限）を max(P[0], P[N-1]) に設定することで、無意味な探索を減らすことができます。

• ダイクストラ法のキュー追加条件に nd <= T を設けることで、\(T\) を超える経路の探索を枝刈りし、定数倍の高速化を図っています。

  ソースコード

import sys
import heapq
import bisect

def solve():
    input = sys.stdin.readline
    N, M, T = map(int, input().split())
    P = list(map(int, input().split()))
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append((v, w))
        adj[v].append((u, w))
        
    def check(X):
        if P[N-1] > X:
            return False
        dist = [T + 1] * N
        dist[0] = 0
        pq = [(0, 0)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            if u == N - 1:
                return True
            for v, w in adj[u]:
                if P[v] <= X:
                    nd = d + w
                    if nd < dist[v]:
                        dist[v] = nd
                        if nd <= T:
                            heapq.heappush(pq, (nd, v))
        return dist[N-1] <= T

    vals = sorted(list(set(P)))
    min_req = max(P[0], P[N-1])
    low = bisect.bisect_left(vals, min_req)
    high = len(vals) - 1
    ans = -1
    while low <= high:
        mid = (low + high) // 2
        if check(vals[mid]):
            ans = vals[mid]
            high = mid - 1
        else:
            low = mid + 1
    print(ans)

if __name__ == '__main__':
    solve()

---

この解説は or-glm5.2-high によって生成されました。