제출 #1147995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147995		fatman87878	Airplane (NOI23_airplane)	C++20	100 / 100	356 ms	16644 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=2e5+5;

int n,m,h[maxN],dis[2][maxN];

vector<int> adj[maxN];

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

inline void dijkstra(int idx,int s){
    fill(dis[idx],dis[idx]+n+1,1e9);
    pq.emplace(dis[idx][s]=0,s);
    for(;!pq.empty();){
        auto [d,u] = pq.top();
        pq.pop();
        if(d!=dis[idx][u])continue;
        for(int v:adj[u])if(dis[idx][v]>max(h[v],d+1))pq.emplace(dis[idx][v]=max(h[v],d+1),v);
    }
}

int main(){
    IOS
    cin>>n>>m;
    for(int i = 1;i<=n;i++)cin>>h[i];
    for(int a,b;m--;)cin>>a>>b,adj[adj[a].emplace_back(b)].emplace_back(a);
    dijkstra(0,1);
    dijkstra(1,n);
    int ans = 1e9;
    for(int i = 1;i<=n;i++){
        ans = min(ans,2*max(dis[0][i],dis[1][i]));
        for(int v:adj[i])ans = min(ans,2*max(dis[0][i],dis[1][v])+1);
    }
    cout<<ans<<'\n';
}

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