Submission #1171905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171905		KhoaDuy	Airplane (NOI23_airplane)	C++17	100 / 100	176 ms	17448 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<int> dijik(int s,int a[],vector<vector<int>> &graph,int n){
    vector<int> bst(n+1);
    for(int i=1;i<=n;i++){
        bst[i]=1e9;
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,s});
    bst[s]=0;
    while(!pq.empty()){
        int u=pq.top().second,dist=pq.top().first;
        pq.pop();
        if(dist>bst[u]){
            continue;
        }
        for(int v:graph[u]){
            int w=max(1,a[v]-dist);
            if(dist+w<bst[v]){
                bst[v]=dist+w;
                pq.push({bst[v],v});
            }
        }
    }
    return bst;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    vector<vector<int>> graph(n+1);
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> bst1=dijik(1,a,graph,n);
    vector<int> bstn=dijik(n,a,graph,n);
    int ans=1e9;
    for(int u=1;u<=n;u++){
        ans=min(ans,2*max(bst1[u],bstn[u]));
    }
    for(int u=1;u<=n;u++){
        for(int v:graph[u]){
            ans=min(ans,2*max(bst1[u],bstn[v])+1);
        }
    }
    cout << ans;
}

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