제출 #1172618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172618		DangKhoizzzz	Airplane (NOI23_airplane)	C++17	100 / 100	212 ms	25796 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair <int , int>
#define fi first
#define se second

using namespace std;

const int INF = 1e18;
const int maxn = 2e5 + 7;

int n , m , a[maxn];
vector <int> g[maxn];

vector <int> dijkstra(int st)
{
    vector <int> d(n+1 , INF);
    vector <bool> vis(n+1 , false);
    priority_queue <pii , vector <pii> , greater <pii>> PQ;
    d[st] = 0;
    PQ.push({0 , st});

    while(!PQ.empty())
    {
        int u = PQ.top().se;
        PQ.pop();
        if(vis[u]) continue;
        vis[u] = 1;

        for(int v: g[u])
        {
            int neww = max(d[u] + 1 , a[v]);
            if(neww < d[v])
            {
                d[v] = neww;
                PQ.push({d[v] , v});
            }
        }
    }
    return d;
}

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);
    }

    vector <int> d1 = dijkstra(1);
    vector <int> dn = dijkstra(n);

    int ans = INF;


    for(int i = 1; i <= n; i++)
    {
        ans = min(ans , max(d1[i] * 2 , dn[i] * 2));

        for(int v: g[i])
        {
            ans = min(ans , max(d1[i]*2 , dn[v]*2) + 1);
            ans = min(ans , max(d1[v]*2 , dn[i]*2) + 1);
        }
    }

    cout << ans << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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