実際の最高標高の最小値を求めるのではなく、以下の判定問題を解けるかを考えます。

標高が \(X\) 以下の地点のみを選んで通過地点が \(K\) 以下となるルートが存在するか。

これは各登山道について標高が高い方が \(X\) 以下ならば有効な登山道とし、有効な登山道についてそれぞれを重み \(1\) の辺として 地点 \(1\) から地点 \(N\) までの最短路問題を解けば判定できます。

先ほどの判定問題が解けるということは答えで二分探索をすることが可能です。実際の答えは判定問題でルートが存在するような \(X\) の最小値となります。

よって、時間計算量は \(\mathrm{O}((N+M) \log H)\) で解くことができます。

実装の際には、答えが存在しないかの判定を別途する必要はなく、二分探索で初めに判定問題で可能となる \(X\) を \(10^9+1\) にし、これが二分探索後に \(10^9\) 以下にならないかで判定すればよいです。

また、答えを \(A\) とすると、\(H_i=A\) となる \(i\) が必ず存在するので、答えを \(N\) 通りにすることができ、時間計算量 \(\mathrm{O}((N+M) \log N)\) で解くこともできます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> h(n);
    for (auto& e : h) cin >> e;
    vector<pair<int, int>> es(m);
    for (auto& [u, v] : es) {
        cin >> u >> v;
        u--, v--;
    }
    int ok = 1000000001, ng = 0;
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;
        vector<vector<int>> g(n);
        for (auto [u, v] : es) {
            if (max(h[u], h[v]) <= mid) g[u].emplace_back(v), g[v].emplace_back(u);
        }
        queue<int> que;
        que.emplace(0);
        vector<int> dist(n, 1000000000);
        dist[0] = 0;
        while (!que.empty()) {
            auto v = que.front();
            que.pop();
            for (auto u : g[v]) {
                if (dist[u] == 1000000000) {
                    dist[u] = dist[v] + 1;
                    que.emplace(u);
                }
            }
        }
        if (dist[n - 1] <= k - 1)
            ok = mid;
        else
            ng = mid;
    }
    if (ok == 1000000001)
        cout << -1 << endl;
    else
        cout << ok << endl;
}