Untitled
unknown
plain_text
4 years ago
1.3 kB
7
Indexable
#include <bits/stdc++.h> using namespace std; #define ll long long int main() { int n, a, b; cin >> n >> a >> b; --a; --b; vector<int> t(n); for (int i = 0; i < n; i++) cin >> t[i]; int x, y; vector<vector<int>> g(n); while (cin >> x >> y) { --x; --y; g[x].push_back(y); g[y].push_back(x); } vector<bool> vis(n); function<void(int, int)> dfs = [&](int u, int th) { vis[u] = true; for (int v: g[u]) { if (!vis[v] && abs(t[u] - t[v]) <= th) { dfs(v, th); } } }; auto ok = [&](int th) { fill(vis.begin(), vis.end(), false); dfs(a, th); return vis[b]; }; int l = 0, r = 30000, mid, best = -1; while (l <= r) { mid = (l + r) / 2; if (ok(mid)) { best = mid; r = mid - 1; } else { l = mid + 1; } } fill(vis.begin(), vis.end(), false); vector<int> parent(n); parent[a] = -1; function<void(int)> dfs2 = [&](int u) { vis[u] = true; for(int v: g[u]) { if(!vis[v] && abs(t[u] - t[v]) <= best) { parent[v] = u; dfs2(v); } } }; cout << best << endl; dfs2(a); vector<int> ans; while(b != -1) { ans.push_back(b); b = parent[b]; } reverse(ans.begin(), ans.end()); for(int z: ans) cout << z + 1 << " "; cout << endl; return 0; }
Editor is loading...