제출 #1178473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178473		prideliqueee	Airplane (NOI23_airplane)	C++20	100 / 100	199 ms	32048 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
struct st
{
    int u,w;
    bool operator < (const st&o) const
    {
        return w>o.w;
    }
};
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    int a[n+1];
    for(int i=1;i<=n;i++)
    cin>>a[i];
    vector<pair<int,int>> ad[n+1];
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        ad[x].push_back({y,a[y]});
        ad[y].push_back({x,a[x]});
    }
    int dist[n+1];
    memset(dist,127,sizeof dist);
    dist[1]=0;
    priority_queue<st> q;
    q.push({1,0});
    while(!q.empty())
    {
        auto p=q.top();
        q.pop();
        int u=p.u,w=p.w;
        if(dist[u]<w)
        continue;
        for(auto x:ad[u])
        {
            if(dist[x.f]>max(x.s,w+1))
            {
                dist[x.f]=max({x.s,w+1});
                q.push({x.f,dist[x.f]});
            }
        }
    }
    
    int dist1[n+1];
    memset(dist1,127,sizeof dist);
    dist1[n]=0;
    q.push({n,0});
    while(!q.empty())
    {
        auto p=q.top();
        q.pop();
        int u=p.u,w=p.w;
        if(dist1[u]<w)
        continue;
        for(auto x:ad[u])
        {
            if(dist1[x.f]>max(x.s,w+1))
            {
                dist1[x.f]=max({x.s,w+1});
                q.push({x.f,dist1[x.f]});
            }
        }
    }
    
    int ans=LLONG_MAX;
    for(int i=1;i<=n;i++)
    {
        ans=min(ans,max(dist[i],dist1[i])*2);
        for(auto x:ad[i])
        {
            ans=min(ans,max(dist[i],dist1[x.f])*2+1);
            ans=min(ans,max(dist1[i],dist[x.f])*2+1);
        }
    }
    cout<<ans;
}

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