危険度が \(X\) 以下であるような地点だけを通って地点 \(1\) から地点 \(N\) まで行くときにかかる最短の所要時間を求めることができれば、これを \(O(\log N)\) 回繰り返すことで元の問題を解くことができます。

上の問題は、危険度が \(X\) 以下の地点どうしを結ぶ辺のみを使って Dijkstra 法などを行うことで \(O((N+M)\log N)\) 時間で解くことができます。

よって、全体で \(O((N+M)(\log N)^2)\) 時間でこの問題を解くことができ、これは十分高速です。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
    int N, M, T;
    cin >> N >> M >> T;
    vector<int> P(N);
    for (int& p : P) {
        cin >> p;
    }

    vector<vector<tuple<int, int>>> edges(N);
    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v; // 0-indexed にしておく
        edges[u].emplace_back(v, w);
        edges[v].emplace_back(u, w);
    }

    // 危険度が X 以下の地点だけを使って地点 1 から地点 N まで移動するとき、所要時間が T を越えてしまうか判定する関数
    auto check = [N, T, P, &edges](int X) {
        // 地点 1 の危険度が X を越えていたらダメ
        if (P[0] > X) return true;

        // Dijkstra 法で所要時間を求める
        vector distance(N, N * 1000000001l);
        priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> pq;
        pq.emplace(distance[0] = 0, 0);

        while (!pq.empty()) {
            auto [d, now] = pq.top();
            pq.pop();
            if (distance[now] < d) {
                continue;
            }
            if (now == N - 1) { // 地点 N に到達したら
                return d > T; // 所要時間が T 以下か判定
            }
            for (auto [next, weight] : edges[now]) {
                // 危険度が X 以下の頂点だけ遷移を行う
                if (P[next] <= X && distance[next] > d + weight) {
                    pq.emplace(distance[next] = d + weight, next);
                }
            }
        }
        return true;
    };

    // ソートして二分探索
    ranges::sort(P);
    cout << *ranges::partition_point(P, check) << endl;
    return 0;
}

from heapq import heappush, heappop


N, M, T = map(int, input().split())
P = list(map(int, input().split()))

edges = [[] for i in range(N)]
for i in range(M):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1 # 0-indexed にしておく
    edges[u].append((v, w))
    edges[v].append((u, w))

# 危険度が X 以下の地点だけを使って地点 1 から地点 N まで移動するとき、所要時間が T を越えてしまうか判定する関数
def check(X):
    # 地点 1 の危険度が X を越えていたらダメ
    if P[0] > X:
        return False

    # Dijkstra 法で所要時間を求める
    distance = [N * 1000000001 for i in range(N)]
    distance[0] = 0
    pq = []
    heappush(pq, (0, 0))

    while len(pq) > 0:
        dist, now = heappop(pq)
        if distance[now] < dist:
            continue
        if now == N - 1: # 地点 N に到達したら
            return dist <= T # 所要時間が T 以下か判定
        for next, weight in edges[now]:
            # 危険度が X 以下の頂点だけ遷移を行う
            if P[next] <= X and distance[next] > dist + weight:
                distance[next] = dist + weight
                heappush(pq, (dist + weight, next))

# 二分探索で答えを求める
L = -1
R = 1000000001
while L + 1 < R:
    M = (L + R) // 2
    if check(M):
        R = M
    else:
        L = M

print(R)