| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1343947 | jump | Airplane (NOI23_airplane) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
int n,m;
int alt[200100];
std::vector<int> adj[200100];
int dist[3][200100];
int highest[3][200100];
int djikstra(int first,int idx){
std::priority_queue<std::pair<int,int>> pq;
for(int i=0;i<=n;i++){
dist[idx][i]=1e9;
}
pq.push({-0,first});
dist[idx][first]=0;
while(!pq.empty()){
auto weight = -pq.top().first;
//int weight = -pair
int curr = pq.top().second;
pq.pop();
for(auto to:adj[curr]){
if(dist[idx][to]>std::max(alt[to],weight+1)){
pq.push({-(std::max(alt[to],weight+1)),to});
dist[idx][to]=std::min(dist[idx][to],std::max(alt[to],weight+1));
highest[idx][to]=std::max(1+highest[idx][curr],alt[to]);
}
if(dist[idx][to]==std::max(alt[to],weight+1)){
highest[idx][to]=std::min(highest[idx][to],std::max(1+highest[idx][curr],alt[to]));
}
}
}
return 0;
}
signed main() {
std::cin >> n >> m;
for(int i=1;i<=n;i++){
int inal;
std::cin >> inal;
alt[i]=inal;
}
for(int i=0;i<m;i++){
int n1,n2;
std::cin >> n1 >> n2;
adj[n1].push_back(n2);
adj[n2].push_back(n1);
}
djikstra(1,0);
djikstra(n,1);
int min = 1e9;
for(int i=1;i<=n;i++){
min=std::min(min,(int)2*std::max(disS[i], disE[i]));
for(int j:adj[i]){
min=std::min(min,(int)2*std::max(disS[i],disE[j])+(int)1);
}
}
std::cout << min;
}