Submission #1272548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272548		goulthen	Airplane (NOI23_airplane)	C++20	0 / 100	71 ms	33308 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back

const int MAXN = 2e5+10;
const int INF = 1e18 + 5;
const int MOD = 1e9+7;
vector<pii> g[MAXN][2];
int dist[MAXN][2],a[MAXN],n;
bool mk[MAXN];

void dijkstra(int u, int k) {
    rep(i,1,n) mk[i] = 0;
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,u});
    dist[u][k] = 0;

    while(!pq.empty()) {
        auto [d,cur] = pq.top();pq.pop();
        if (mk[cur]) continue;
        mk[cur] = 1;

        for (auto &[v,w] : g[cur][k]) {
            if (dist[v][k] <= d + w) continue;
            dist[v][k] = d+w;
            pq.push({d+w,v});
        }
    }
}

void solve() {
    int m;cin >> n >> m;
    rep(i,1,n) cin >> a[i], dist[i][0] = dist[i][1] = INF;  

    rep(i,1,m) {
        int u,v;cin >> u >> v;
        g[u][0].pb({v,max(1LL,a[v]-a[u])});
        g[v][0].pb({u,max(1LL,a[u]-a[v])});
        g[v][1].pb({u,max(1LL,a[u]-a[v])});
        g[u][1].pb({v,max(1LL,a[v]-a[u])});
    }

    dijkstra(1,0);
    dijkstra(n,1);

    int ans = INF;
    rep(i,1,n) ans = min(ans, dist[i][0] + dist[i][1] + max(0LL,abs(dist[i][0]-dist[i][1])-1));
    //rep(i,1,n) cout << i << ' ' << dist[i][0] << ' ' << dist[i][1] << '\n';
    cout << ans << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;

    while (tt--) solve();
    return 0;
}

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