제출 #1171923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171923		fryingduc	Airplane (NOI23_airplane)	C++20	100 / 100	292 ms	17540 KiB

Main

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int M = 4e5 + 5;
int n, m;
vector<int> g[maxn];
int a[maxn];
int d[2][maxn];

void dijkstra(int src, int d[]) {
  fill(d, d + n + 1, 1e9);
  using T = pair<int, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.emplace(0, src);
  d[src] = 0;
  while (!pq.empty()) {
    auto [dist, u] = pq.top();
    pq.pop();
    if (dist > d[u]) continue;
    for (auto v : g[u]) {
      int w = max(1, a[v] - dist);
      if (d[v] > dist + w) {
        d[v] = dist + w;
        pq.emplace(d[v], v);
      }
    }
  }
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dijkstra(1, d[0]);
  dijkstra(n, d[1]);
  
  int res = 2e9;
  
  for (int i = 1; i <= n; ++i) {
    res = min(res, 2 * max(d[0][i], d[1][i]));
    for (auto v : g[i]) {
      res = min(res, 2 * max(d[0][i], d[1][v]) + 1);
    }
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 10 / 10
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37