oj.uz

Submission #914214

# Submission time Handle Problem Language Result Execution time Memory
914214 2024-01-21T11:16:49 Z esomer Airplane (NOI23_airplane) C++17
0 / 100
 74 ms 16128 KB 
#include<bits/stdc++.h>
 
using namespace std;

#define int long long

vector<int> Dijkstra(int start, vector<vector<int>>& adj, vector<int>& a){
    int n = (int)adj.size();
    vector<int> dist(n, 1e18);
    vector<bool> vis(n, false);
    dist[start] = 0;
    priority_queue<pair<int, int>> q; q.push({0, start});
    while(!q.empty()){
        int x = q.top().second; q.pop();
        if(vis[x]) continue;
        vis[x] = true;
        for(int& node : adj[x]){
            if(dist[node] > max(a[node], dist[x] + 1)){
                dist[node] = max(a[node], dist[x] + 1);
                q.push({-dist[node], node});
            }
        }
    }
    return dist;
}

void solve(){
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for(auto &i : a) cin >> i;
    vector<vector<int>> adj(n);
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> dist1 = Dijkstra(0, adj, a);
    vector<int> distN = Dijkstra(n-1, adj, a);
    int ans = 1e18;
    for(int i = 0; i < n; i++){
        int cost = max(dist1[i], distN[i]) * 2;
        if(abs(dist1[i] - distN[i]) == 1 && min(dist1[i], distN[i]) >= 1) cost--;
        ans = min(ans, cost);
    }
    cout << ans << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // int tt; cin >> tt;
    int tt = 1;
    while(tt--) solve();
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 59 ms 16092 KB Output is correct
3 Correct 74 ms 16004 KB Output is correct
4 Correct 62 ms 15956 KB Output is correct
5 Correct 65 ms 16128 KB Output is correct
6 Correct 65 ms 16100 KB Output is correct
7 Correct 63 ms 15960 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 59 ms 16092 KB Output is correct
3 Correct 74 ms 16004 KB Output is correct
4 Correct 62 ms 15956 KB Output is correct
5 Correct 65 ms 16128 KB Output is correct
6 Correct 65 ms 16100 KB Output is correct
7 Correct 63 ms 15960 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -