题解

路线可以任意选择起点，也可以重复经过站点．因此，限制答案不超过 $W$，就等价于只使用点权不超过 $W$ 的站点，问能否连续访问 $k$ 次．这里统计的是点的访问次数，不是道路数．

算法 0：只访问一两次

$k=1$ 时不需要道路，直接选择点权最小的站点．$k=2$ 时恰好走一条边，枚举每条边 $u\to v$，取 $\max(a_u,a_v)$ 的最小值；没有边就无解．复杂度 $O(n+m)$，额外空间 $O(1)$．

预期通过子任务 1，获得 10 分．

算法 1：按访问次数计算最优费用

设 $f_t(v)$ 表示恰好访问 $t$ 次、最后停在 $v$ 时，路线所需通行等级的最小值．初始 $f_1(v)=a_v$．对于每条边 $u\to v$，有转移：

不可达状态设为比 $10^9$ 大的数．最后取 $\min_v f_k(v)$．因为任何一条非空移动的路线都能删除最后一条边，变成某个前驱的路线，这个转移既不漏掉合法路线，也不会引入非法路线．

必须使用前后两层数组，不能在同一层原地更新，否则会把多次移动混为一次．每一层扫描全部点和边，时间 $O(k(n+m))$，滚动数组空间 $O(n+m)$（包括存图）．

预期通过子任务 1、2，获得 25 分．完整数据中 $k$ 可以达到 $10^{18}$，不能逐步推进．

算法 2：道路构成一条有向链

在子任务 3 中，一条路线只能是连续的站点 $l,l+1,\ldots,l+k-1$．若 $k>n$，无解；否则枚举长度为 $k$ 的连续窗口，取窗口最大点权的最小值．

单调队列维护窗口最大值：从队尾删除不大于新点权的旧位置，再插入新位置；从队头删除离开窗口的位置．被新位置删除的旧位置更靠左、点权也不更大，在后续窗口中不可能比新位置更有用．每个位置只入队、出队一次，时间 $O(n)$，空间 $O(n)$．

预期通过子任务 3，获得 15 分．可以与算法 1 的小范围分支合并，但不能把任意图按照编号当作一条链．

算法 3：先解决“能不能走够次数”

子任务 4 的点权都相等．只要存在合法路线，答案就是这个共同点权，不需要优化费用．

图中有有向环时，可以从环上的某个点出发，沿环重复走，并在访问次数达到 $k$ 时立即停下．不需要完整绕若干圈，所以 $k$ 不需要是环长的倍数．

图中没有有向环时，一条路线不会重复经过点，否则两次经过之间的部分就形成了环．此时求 DAG 的最长路即可．把每个点作为起点时长度初始化为 $1$，按拓扑序对每条边 $u\to v$ 更新：

拓扑序保证处理 $v$ 前，所有可能的前驱都已处理，因此 $d_v$ 恰好是终点为 $v$ 的最长路线点数．若最大值至少为 $k$，截取这条路线的前 $k$ 次访问即可；否则无解．

拓扑排序还可以同时判环：把入度为 $0$ 的点不断删除，如果最终没有删完全部点，剩余图中每个点都有剩余前驱，沿前驱不断走必然重复遇到点，因此存在有向环．反过来，环上每个点都保留着来自环内的入边，不能全部被删除．

一次计算时间 $O(n+m)$，空间 $O(n+m)$．预期通过子任务 4，获得 10 分．

算法 4：无环图上的二分答案

如果答案不超过 $W$，那么一定不会经过点权大于 $W$ 的站点；反过来，只要剩余站点之间存在足够长的路线，它就满足费用限制．因此只保留 $a_i\le W$ 的点以及两端均保留的边，然后求最长路，判断长度是否至少为 $k$．

随着 $W$ 增大，允许使用的站点和边只会增加，原有合法路线不会消失，所以可行性具有单调性．任何实际路线的费用都等于某个点权，因此将点权排序去重后，在这些值中二分第一个可行值．如果最大点权也不可行，则输出 $-1$．

子任务 5 保证原图无环，删点后的图也无环，不需要额外考虑环．复杂度 $O((n+m)\log n)$，空间 $O(n+m)$．预期通过子任务 3、5；与已述小范围及等权分支合并，可保证获得前五组共 70 分．

算法 5：完整解法

对于任意图，仍然二分通行等级，只是在每次判定中同时考虑上面的两种情况：

• 保留的图中有有向环：可行．
• 没有有向环：最长路线访问次数至少为 $k$ 时可行．

执行拓扑排序时维护最长路．只要某个已取出的点满足 $d_u\ge k$，就可以提前返回可行；否则继续删除点．若最终删除数小于保留点数，则存在有向环，也返回可行．两者都不满足才不可行．注意比较的是保留点数，不是原图的 $n$，被费用限制排除的点不应被当作环上的点．

这一判定是充要的：算法返回可行时，或者已经找到足够长的实际路线，或者可以在实际存在的环上走出要求次数；如果有合法路线却未找到足够长的拓扑路线，那么该图不能是 DAG，只能含环，而判环分支一定会接受．结合答案单调性，二分得到的就是最低通行等级．

初始化和每次判定均只扫描点与边，最多判定 $O(\log n)$ 次；加上点权排序，时间 $O((n+m)\log n)$，空间 $O(n+m)$．$k$ 要使用 long long；DAG 最长路不超过 $n$，长度数组使用 int 即可．实现不使用递归，避免长链造成调用栈过深．

预期通过所有子任务，获得 100 分．

参考代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    long long k;
    cin >> n >> m >> k;
    vector<int> a(n), values;
    for (int &x : a) cin >> x;
    values = a;
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    vector<vector<int>> g(n);
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
    }
    vector<int> deg(n), dp(n), que(n);
    auto check = [&](int limit) {
        fill(deg.begin(), deg.end(), 0);
        fill(dp.begin(), dp.end(), 1);
        int active = 0, head = 0, tail = 0;
        for (int u = 0; u < n; ++u) if (a[u] <= limit) {
            ++active;
            for (int v : g[u]) if (a[v] <= limit) ++deg[v];
        }
        for (int u = 0; u < n; ++u)
            if (a[u] <= limit && deg[u] == 0) que[tail++] = u;
        while (head < tail) {
            int u = que[head++];
            if (dp[u] >= k) return true;
            for (int v : g[u]) if (a[v] <= limit) {
                dp[v] = max(dp[v], dp[u] + 1);
                if (--deg[v] == 0) que[tail++] = v;
            }
        }
        // 未被拓扑排序删除的点中存在有向环，可反复绕行．
        return head < active;
    };
    if (!check(values.back())) {
        cout << -1 << '\n';
        return 0;
    }
    int l = 0, r = int(values.size()) - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(values[mid])) r = mid;
        else l = mid + 1;
    }
    cout << values[l] << '\n';
}