#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5;
int n, m, a[nx], u, v, vl[nx], rvl[nx], vs[nx], dist[nx], res=1e9;
vector<int> d[nx];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=n; i++) cin>>a[i], vl[i]=rvl[i]=1e9;
for (int i=1; i<=m; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
vl[1]=rvl[n]=0;
pq.push({0, 1});
while (!pq.empty())
{
auto [cw, u]=pq.top();
pq.pop();
if (vs[u]) continue;
vs[u]=1;
for (auto v:d[u]) if (vl[v]>max(cw+1, a[v])) vl[v]=max(cw+1, a[v]), pq.push({vl[v], v});
}
pq.push({0, n});
for (int i=1; i<=n; i++) vs[i]=0;
while (!pq.empty())
{
auto [cw, u]=pq.top();
pq.pop();
if (vs[u]) continue;
vs[u]=1;
for (auto v:d[u]) if (rvl[v]>max(cw+1, a[v])) rvl[v]=max(cw+1, a[v]), pq.push({rvl[v], v});
}
/*
cout<<"vl ";
for (int i=1; i<=n; i++) cout<<vl[i]<<' ';
cout<<'\n';
cout<<"rvl ";
for (int i=1; i<=n; i++) cout<<rvl[i]<<' ';
cout<<'\n';
*/
for (int t=1; t<=n; t++)
{
int mx=a[t];
for (int i=1; i<=n ;i++) dist[i]=1e9, vs[i]=0;
for (int i=1; i<=n; i++) if (vl[i]<=mx) dist[i]=0, pq.push({0, i});
while (!pq.empty())
{
auto [cw, u]=pq.top();
pq.pop();
if (vs[u]) continue;
vs[u]=1;
for (auto v:d[u]) if (a[v]<=mx&&dist[v]>cw+1) dist[v]=cw+1, pq.push({dist[v], v});
}
for (int i=1; i<=n; i++) if (rvl[i]<=mx) res=min(res, 2*mx+dist[i]);
}
cout<<res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8784 KB |
Output is correct |
2 |
Execution timed out |
1083 ms |
15244 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8784 KB |
Output is correct |
2 |
Correct |
2 ms |
8784 KB |
Output is correct |
3 |
Correct |
2 ms |
8784 KB |
Output is correct |
4 |
Correct |
2 ms |
8784 KB |
Output is correct |
5 |
Correct |
2 ms |
8816 KB |
Output is correct |
6 |
Correct |
14 ms |
8784 KB |
Output is correct |
7 |
Correct |
52 ms |
8972 KB |
Output is correct |
8 |
Correct |
19 ms |
8784 KB |
Output is correct |
9 |
Correct |
99 ms |
8784 KB |
Output is correct |
10 |
Correct |
27 ms |
8956 KB |
Output is correct |
11 |
Correct |
116 ms |
8952 KB |
Output is correct |
12 |
Correct |
33 ms |
8784 KB |
Output is correct |
13 |
Correct |
102 ms |
8784 KB |
Output is correct |
14 |
Correct |
112 ms |
8976 KB |
Output is correct |
15 |
Correct |
119 ms |
8784 KB |
Output is correct |
16 |
Correct |
128 ms |
9000 KB |
Output is correct |
17 |
Correct |
109 ms |
8784 KB |
Output is correct |
18 |
Correct |
2 ms |
8784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8784 KB |
Output is correct |
2 |
Correct |
2 ms |
8784 KB |
Output is correct |
3 |
Correct |
2 ms |
8784 KB |
Output is correct |
4 |
Correct |
2 ms |
8784 KB |
Output is correct |
5 |
Correct |
2 ms |
8816 KB |
Output is correct |
6 |
Correct |
14 ms |
8784 KB |
Output is correct |
7 |
Correct |
52 ms |
8972 KB |
Output is correct |
8 |
Correct |
19 ms |
8784 KB |
Output is correct |
9 |
Correct |
99 ms |
8784 KB |
Output is correct |
10 |
Correct |
27 ms |
8956 KB |
Output is correct |
11 |
Correct |
116 ms |
8952 KB |
Output is correct |
12 |
Correct |
33 ms |
8784 KB |
Output is correct |
13 |
Correct |
102 ms |
8784 KB |
Output is correct |
14 |
Correct |
112 ms |
8976 KB |
Output is correct |
15 |
Correct |
119 ms |
8784 KB |
Output is correct |
16 |
Correct |
128 ms |
9000 KB |
Output is correct |
17 |
Correct |
109 ms |
8784 KB |
Output is correct |
18 |
Correct |
2 ms |
8784 KB |
Output is correct |
19 |
Correct |
25 ms |
8784 KB |
Output is correct |
20 |
Correct |
17 ms |
8784 KB |
Output is correct |
21 |
Correct |
28 ms |
8784 KB |
Output is correct |
22 |
Correct |
58 ms |
8784 KB |
Output is correct |
23 |
Correct |
14 ms |
8784 KB |
Output is correct |
24 |
Correct |
39 ms |
8924 KB |
Output is correct |
25 |
Correct |
47 ms |
8784 KB |
Output is correct |
26 |
Correct |
91 ms |
9064 KB |
Output is correct |
27 |
Correct |
103 ms |
8784 KB |
Output is correct |
28 |
Correct |
90 ms |
9016 KB |
Output is correct |
29 |
Correct |
115 ms |
8784 KB |
Output is correct |
30 |
Correct |
87 ms |
9016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8784 KB |
Output is correct |
2 |
Execution timed out |
1083 ms |
15244 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |