二分 + 记忆化搜索
答案是单调的，所以直接二分答案，然后检查的时候就记忆化搜索，看看在限制当前最高值的情况下，能不能走 k 步，如果走的发现是个环，则直接返回可以走 k 步就行
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define pii pair const ll maxn = 2e5 + 10; const ll inf = 1e17 + 10; int num[maxn]; int a[maxn], vis[maxn]; ll dp[maxn]; vectorgra[maxn]; ll n, m, k; ll dps(int now, int x) { if(dp[now]) return dp[now] == -1 ? 0 : dp[now]; if(num[now] > x) {dp[now] = -1; return 0;} vis[now] = 1; ll ans = 0; for(int i=0; i= k; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> k; for(int i=1; i<=n; i++) {cin >> num[i]; a[i] = num[i];} while(m--) { int a, b; cin >> a >> b; gra[a].push_back(b); } sort(a + 1, a + n + 1); int l = 1, r = n; while(l < r) { int mid = l + r >> 1; if(judge(a[mid])) r = mid; else l = mid + 1; } if(judge(a[l])) cout << a[l] << endl; else cout << -1 << endl; return 0; }