Submission #1178417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178417		prideliqueee	Airplane (NOI23_airplane)	C++20	0 / 100	45 ms	19012 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
struct st
{
    int u,w,mx;
    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];
    set<int> ss;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        ad[x].push_back({y,max(a[x],a[y])});
        ad[y].push_back({x,max(a[x],a[y])});
        if(x==n)
        ss.insert(y);
        else if(y==n)
        ss.insert(x);
    }
    pair<int,int> dist[n+1];
    memset(dist,127,sizeof dist);
    dist[1]={0,0};
    priority_queue<st> q;
    q.push({1,0,0});
    while(!q.empty())
    {
        auto p=q.top();
        q.pop();
        int u=p.u,w=p.w,mx=p.mx;
        if(dist[u].f<w||(dist[u].f==w&&dist[u].s>mx))
        continue;
        for(auto x:ad[u])
        {
            int ww;
            if(mx<x.s)
            {
                if(dist[x.f].f>w+(x.s-mx)*2)
                {
                    dist[x.f].f=w+(x.s-mx)*2;
                    dist[x.f].s=x.s;
                    q.push({x.f,w+(x.s-mx)*2,x.s});
                }
            }
            else
            {
                if(dist[x.f].f>w+1||(dist[x.f].f==w+1&&dist[x.s].s>mx))
                {
                    dist[x.f].f=w+1;
                    dist[x.f].s=mx;
                    q.push({x.f,w+1,mx});
                }
            }
        }
    }
    int ans=LLONG_MAX;
    for(auto x:ss)
    {
        ans=min(ans,dist[x].f);
    }
    cout<<ans;
}

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