제출 #1354087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1354087		takoshanava	Airplane (NOI23_airplane)	C++20	0 / 100	100 ms	22336 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 2e5 + 5, INF = 1e18;

int n, m, a[N];
vector<int> adj[N];
vector<pair<int, int>> edg;

vector<int> dij(int s){
    vector<int> d(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    d[s] = 0;
    pq.push({0, s});

    while(pq.size()){
        auto [cw, u] = pq.top(); pq.pop();
        if(cw > d[u]) continue;
        for(auto v:adj[u]){
            int w = max(a[v], d[u] + 1);
            if(d[v] > w) d[v] = w, pq.push({w, v});
        }
    }
    return d;
}

signed main(){
    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;
        adj[u].pb(v);
        adj[v].pb(u);
        edg.pb({u, v});
        edg.pb({v, u});
    }

    vector<int> mn1 = dij(1), mn2 = dij(n);
    int ans = INF;
    for(int i = 0; i <= n; i++) ans = min(ans, 2 * max(mn1[i], mn2[i]));

    cout << ans << endl;
}

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