oj.uz

Submission #761634

# Submission time Handle Problem Language Result Execution time Memory
761634 2023-06-20T06:31:03 Z gggkik None (JOI14_ho_t4) C++14
25 / 100
 110 ms 19760 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
using pii = pair<int,int>;
const int MXN = 1e5+5;
vector<pii> E[MXN];
ll h[MXN], d[MXN];
int n,m,s;
void dijkstra(int x){
    priority_queue<pii> pq; pq.push({0,x});
    for(int i = 2;i<=n;i++) d[i] = 1LL<<62;
    for(;pq.size();){
        x = pq.top().second; pq.pop();
        for(auto i : E[x]) if(h[x]>=i.second && d[i.first]>d[x]+i.second*2){
            d[i.first] = d[x]+i.second*2;
            pq.push({-d[i.first],i.first});
        }
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> s;
    for(int i = 1;i<=n;i++) cin >> h[i];
    for(int i = 0;i<m;i++){
        int a,b,c; cin >> a >> b >> c;
        E[a].push_back({b,c});
        E[b].push_back({a,c});
    }
    dijkstra(1);
    if(d[n]==1LL<<62) cout << -1;
    else cout << d[n]+h[n];
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 19760 KB Output is correct
2 Correct 100 ms 17020 KB Output is correct
3 Correct 64 ms 11624 KB Output is correct
4 Correct 99 ms 17308 KB Output is correct
5 Correct 79 ms 15944 KB Output is correct
6 Correct 5 ms 3412 KB Output is correct
7 Correct 96 ms 18188 KB Output is correct
8 Correct 97 ms 16616 KB Output is correct
9 Correct 90 ms 17912 KB Output is correct
10 Correct 61 ms 14284 KB Output is correct
11 Correct 11 ms 4180 KB Output is correct
12 Correct 60 ms 12460 KB Output is correct
13 Correct 28 ms 8696 KB Output is correct
14 Correct 94 ms 17900 KB Output is correct
15 Correct 4 ms 3156 KB Output is correct
16 Correct 77 ms 15608 KB Output is correct
17 Correct 9 ms 4172 KB Output is correct
18 Correct 11 ms 4564 KB Output is correct
19 Correct 37 ms 9332 KB Output is correct
20 Correct 12 ms 4680 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2816 KB Output isn't correct
3 Halted 0 ms 0 KB -