Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
1.3 kB
3
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;
}