#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 2e5+5;
int n, m;
ll a[mxN], dis[mxN], ans = LLONG_MAX;
vector <int> adj[mxN];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0, u, v; i < m; i++) cin >> u >> v, adj[u].emplace_back(v), adj[v].emplace_back(u);
priority_queue <tuple <ll, ll, ll, int>> q;
q.emplace(0, 0, 0, 1);
for (int i = 2; i <= n; i++) dis[i] = LLONG_MAX;
while (!q.empty()) {
auto [t, L, R, u] = q.top(); q.pop();
if (u == n) { ans = min(ans, (-t) + R); continue; }
for (auto v : adj[u]) {
ll w = 1, l = L, r = R;
if (a[v] > l) w = a[v] - l, l = a[v];
r--;
r = max(r, a[v]);
if (dis[v] > dis[u] + w) q.emplace(-(dis[v] = dis[u] + w), l, r, v);
}
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |