제출 #1361356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361356		lyra_g13	Airplane (NOI23_airplane)	C++20	100 / 100	214 ms	28084 KiB

Main

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, m;
  cin >> n >> m;

  vector<ll> a(n);
  for (auto &i : a) {
    cin >> i;
  }
  vector<vector<ll>> adj(n);
  for (int i = 0; i < m; i++) {
    ll u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  for (int i = 0; i < n; i++) {
    adj[i].push_back(i);
  }

  auto bfs = [&](ll u) {
    vector<ll> dist(n, 1e18);
    dist[u] = 0;
    priority_queue<pair<ll, ll>> pq;
    pq.push({0, u});

    while (!pq.empty()) {
      auto [h, u] = pq.top();
      pq.pop();
      h = -h;

      if (h > dist[u])
        continue;
      for (auto v : adj[u]) {
        if (dist[v] > max(h + 1, a[v])) {
          dist[v] = max(h + 1, a[v]);
          pq.push({-dist[v], v});
        }
      }
    }
    return dist;
  };

  vector<ll> s = bfs(0);
  vector<ll> e = bfs(n - 1);

  ll ans = 1e18;
  for (int i = 0; i < n; i++) {
    ans = min(ans, 2 * max(s[i], e[i]));
    for (auto u : adj[i]) {
      ans = min(ans, 2 * min(max(s[i], e[u]), max(s[u], e[i])) + 1);
    }
  }
  cout << ans << "\n";
}

• 서브태스크 1: 22 / 22
• 서브태스크 2: 10 / 10
• 서브태스크 3: 31 / 31
• 서브태스크 4: 37 / 37