| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 140380 |
2019-08-02T16:53:21 Z |
nhc7502 |
None (JOI14_ho_t4) |
C++14 |
|
373 ms |
28020 KB |
///EVERYONE BELIEVE IN GODTAEGYU
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
long long n, m, i, j, k;
long long x, h[100141];
long long dist[100141];
vector<pair<int,int>>graph[100141];
priority_queue<pair<long long, int>>pq;
int main(){
iostream::sync_with_stdio(0);cin.tie(0);cout.tie(0);
for(cin>>n>>m>>x; i++<n;)
{
cin>>h[i];
dist[i] = -INF;
}
for(;m--;)
{
cin>>i>>j>>k;
if(h[i] >= k)
graph[i].push_back({j, k});
if(h[j] >= k)
graph[j].push_back({i, k});
}
pq.push({x, 1});
while(!pq.empty())
{
tie(m, i) = pq.top();
pq.pop();
if(dist[i] != -INF)continue;
dist[i] = m;
for(auto next : graph[i])
{ //i = 현재 나무, m = 현재 높이, j = 다음 나무, k = 다음 나무 거리
tie(j, k) = next;
pq.push({min(m - k, h[j]), j});
}
}
if(dist[n] == -INF) cout<<-1;
else cout<<x + h[n] - dist[n] * 2;
/*
if 양수 -> 유지할 수 있는 최소 높이
따라서 (x-dist[n]) + (h[n]-dist[n])
if 음수 -> x는 다 쓴 이후 나무사이 가는데 최소거리(올라가는거 고려 X)
따라서 (h[n]-dist[n]) -> 올라가는데 필요한 비용
x-dist[n] -> 날아가는데 필요한 비용
*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 5 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 10 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 13 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 15 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 16 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 17 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 18 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 19 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 20 |
Correct |
5 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
7772 KB |
Output is correct |
| 2 |
Correct |
373 ms |
20160 KB |
Output is correct |
| 3 |
Correct |
175 ms |
9824 KB |
Output is correct |
| 4 |
Correct |
361 ms |
19572 KB |
Output is correct |
| 5 |
Correct |
359 ms |
28020 KB |
Output is correct |
| 6 |
Correct |
11 ms |
2936 KB |
Output is correct |
| 7 |
Correct |
118 ms |
4956 KB |
Output is correct |
| 8 |
Correct |
319 ms |
19712 KB |
Output is correct |
| 9 |
Correct |
136 ms |
10940 KB |
Output is correct |
| 10 |
Correct |
102 ms |
8316 KB |
Output is correct |
| 11 |
Correct |
28 ms |
4472 KB |
Output is correct |
| 12 |
Correct |
169 ms |
14868 KB |
Output is correct |
| 13 |
Correct |
137 ms |
16876 KB |
Output is correct |
| 14 |
Correct |
120 ms |
9976 KB |
Output is correct |
| 15 |
Correct |
9 ms |
3196 KB |
Output is correct |
| 16 |
Correct |
349 ms |
23560 KB |
Output is correct |
| 17 |
Correct |
22 ms |
4216 KB |
Output is correct |
| 18 |
Correct |
26 ms |
4724 KB |
Output is correct |
| 19 |
Correct |
51 ms |
5880 KB |
Output is correct |
| 20 |
Correct |
27 ms |
4728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 5 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 10 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 13 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 15 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 16 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 17 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 18 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 19 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 20 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 21 |
Correct |
200 ms |
7772 KB |
Output is correct |
| 22 |
Correct |
373 ms |
20160 KB |
Output is correct |
| 23 |
Correct |
175 ms |
9824 KB |
Output is correct |
| 24 |
Correct |
361 ms |
19572 KB |
Output is correct |
| 25 |
Correct |
359 ms |
28020 KB |
Output is correct |
| 26 |
Correct |
11 ms |
2936 KB |
Output is correct |
| 27 |
Correct |
118 ms |
4956 KB |
Output is correct |
| 28 |
Correct |
319 ms |
19712 KB |
Output is correct |
| 29 |
Correct |
136 ms |
10940 KB |
Output is correct |
| 30 |
Correct |
102 ms |
8316 KB |
Output is correct |
| 31 |
Correct |
28 ms |
4472 KB |
Output is correct |
| 32 |
Correct |
169 ms |
14868 KB |
Output is correct |
| 33 |
Correct |
137 ms |
16876 KB |
Output is correct |
| 34 |
Correct |
120 ms |
9976 KB |
Output is correct |
| 35 |
Correct |
9 ms |
3196 KB |
Output is correct |
| 36 |
Correct |
349 ms |
23560 KB |
Output is correct |
| 37 |
Correct |
22 ms |
4216 KB |
Output is correct |
| 38 |
Correct |
26 ms |
4724 KB |
Output is correct |
| 39 |
Correct |
51 ms |
5880 KB |
Output is correct |
| 40 |
Correct |
27 ms |
4728 KB |
Output is correct |
| 41 |
Correct |
119 ms |
9300 KB |
Output is correct |
| 42 |
Correct |
36 ms |
5740 KB |
Output is correct |
| 43 |
Correct |
92 ms |
7928 KB |
Output is correct |
| 44 |
Correct |
121 ms |
9968 KB |
Output is correct |
| 45 |
Correct |
299 ms |
19428 KB |
Output is correct |
| 46 |
Correct |
17 ms |
4856 KB |
Output is correct |
| 47 |
Correct |
313 ms |
17620 KB |
Output is correct |
| 48 |
Correct |
335 ms |
19940 KB |
Output is correct |
| 49 |
Correct |
274 ms |
17832 KB |
Output is correct |
| 50 |
Correct |
342 ms |
20200 KB |
Output is correct |
| 51 |
Correct |
31 ms |
5240 KB |
Output is correct |
| 52 |
Correct |
234 ms |
17236 KB |
Output is correct |
| 53 |
Correct |
113 ms |
10104 KB |
Output is correct |
| 54 |
Correct |
140 ms |
10836 KB |
Output is correct |
| 55 |
Correct |
128 ms |
9848 KB |
Output is correct |
| 56 |
Correct |
360 ms |
20336 KB |
Output is correct |
| 57 |
Correct |
57 ms |
7164 KB |
Output is correct |
| 58 |
Correct |
8 ms |
3064 KB |
Output is correct |
| 59 |
Correct |
111 ms |
9692 KB |
Output is correct |
| 60 |
Correct |
50 ms |
7032 KB |
Output is correct |
