# Untitled

unknown
plain_text
2 years ago
1.3 kB
3
Indexable
Never
```#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;
}
```