oj.uz

답안 #761634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761634 2023-06-20T06:31:03 Z gggkik 날다람쥐 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -