| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55158 |
2018-07-06T07:10:01 Z |
khsoo01(#2065) |
None (JOI14_ho_t4) |
C++11 |
|
511 ms |
22456 KB |
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 100005, M = 300005, inf = 1e18;
ll n, m, x, h[N], d[N][2];
vector<pll> adj[N];
priority_queue<pair<ll, pll> > pq;
void upd (ll A, ll B, ll C) {
if(d[A][B] <= C) return;
d[A][B] = C;
pq.push({-C, {A, B}});
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&x);
for(ll i=1;i<=n;i++) {
scanf("%lld",&h[i]);
d[i][0] = d[i][1] = inf;
}
for(ll i=1;i<=m;i++) {
ll A, B, C;
scanf("%lld%lld%lld",&A,&B,&C);
adj[A].push_back({B, C});
adj[B].push_back({A, C});
}
d[1][0] = 0;
pq.push({0, {1, 0}});
while(!pq.empty()) {
ll V = -pq.top().X, C, D;
tie(C, D) = pq.top().Y;
pq.pop();
if(d[C][D] != V) continue;
for(auto &T : adj[C]) {
ll A, B;
tie(A, B) = T;
if(D == 0) {
if(x-h[A] > V+B) {
upd(A, 0, x-h[A]);
}
else if(V+B > x) {
if(h[C] >= B) upd(A, 1, 2*(V+B)-x);
}
else upd(A, 0, V+B);
}
else {
if(h[C] >= B) upd(A, 1, V+2*B);
}
}
}
if(d[n][0] != inf) {
printf("%lld\n",d[n][0] + h[n] - (x - d[n][0]));
}
else if(d[n][1] != inf) {
printf("%lld\n",d[n][1] + h[n]);
}
else puts("-1");
}
Compilation message
2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&n,&m,&x);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&h[i]);
~~~~~^~~~~~~~~~~~~~
2014_ho_t4.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&A,&B,&C);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3156 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 7 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3224 KB |
Output is correct |
| 10 |
Correct |
8 ms |
3224 KB |
Output is correct |
| 11 |
Correct |
4 ms |
3224 KB |
Output is correct |
| 12 |
Correct |
6 ms |
3224 KB |
Output is correct |
| 13 |
Correct |
6 ms |
3224 KB |
Output is correct |
| 14 |
Correct |
5 ms |
3224 KB |
Output is correct |
| 15 |
Correct |
7 ms |
3224 KB |
Output is correct |
| 16 |
Correct |
5 ms |
3224 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3224 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3224 KB |
Output is correct |
| 19 |
Correct |
6 ms |
3224 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
370 ms |
21120 KB |
Output is correct |
| 2 |
Correct |
311 ms |
21360 KB |
Output is correct |
| 3 |
Correct |
201 ms |
21360 KB |
Output is correct |
| 4 |
Correct |
368 ms |
22228 KB |
Output is correct |
| 5 |
Correct |
242 ms |
22228 KB |
Output is correct |
| 6 |
Correct |
12 ms |
22228 KB |
Output is correct |
| 7 |
Correct |
389 ms |
22228 KB |
Output is correct |
| 8 |
Correct |
345 ms |
22228 KB |
Output is correct |
| 9 |
Correct |
244 ms |
22228 KB |
Output is correct |
| 10 |
Correct |
348 ms |
22228 KB |
Output is correct |
| 11 |
Correct |
33 ms |
22228 KB |
Output is correct |
| 12 |
Correct |
200 ms |
22228 KB |
Output is correct |
| 13 |
Correct |
76 ms |
22228 KB |
Output is correct |
| 14 |
Correct |
326 ms |
22228 KB |
Output is correct |
| 15 |
Correct |
12 ms |
22228 KB |
Output is correct |
| 16 |
Correct |
246 ms |
22228 KB |
Output is correct |
| 17 |
Correct |
23 ms |
22228 KB |
Output is correct |
| 18 |
Correct |
31 ms |
22228 KB |
Output is correct |
| 19 |
Correct |
92 ms |
22228 KB |
Output is correct |
| 20 |
Correct |
43 ms |
22228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3156 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 7 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3156 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3224 KB |
Output is correct |
| 10 |
Correct |
8 ms |
3224 KB |
Output is correct |
| 11 |
Correct |
4 ms |
3224 KB |
Output is correct |
| 12 |
Correct |
6 ms |
3224 KB |
Output is correct |
| 13 |
Correct |
6 ms |
3224 KB |
Output is correct |
| 14 |
Correct |
5 ms |
3224 KB |
Output is correct |
| 15 |
Correct |
7 ms |
3224 KB |
Output is correct |
| 16 |
Correct |
5 ms |
3224 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3224 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3224 KB |
Output is correct |
| 19 |
Correct |
6 ms |
3224 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3224 KB |
Output is correct |
| 21 |
Correct |
370 ms |
21120 KB |
Output is correct |
| 22 |
Correct |
311 ms |
21360 KB |
Output is correct |
| 23 |
Correct |
201 ms |
21360 KB |
Output is correct |
| 24 |
Correct |
368 ms |
22228 KB |
Output is correct |
| 25 |
Correct |
242 ms |
22228 KB |
Output is correct |
| 26 |
Correct |
12 ms |
22228 KB |
Output is correct |
| 27 |
Correct |
389 ms |
22228 KB |
Output is correct |
| 28 |
Correct |
345 ms |
22228 KB |
Output is correct |
| 29 |
Correct |
244 ms |
22228 KB |
Output is correct |
| 30 |
Correct |
348 ms |
22228 KB |
Output is correct |
| 31 |
Correct |
33 ms |
22228 KB |
Output is correct |
| 32 |
Correct |
200 ms |
22228 KB |
Output is correct |
| 33 |
Correct |
76 ms |
22228 KB |
Output is correct |
| 34 |
Correct |
326 ms |
22228 KB |
Output is correct |
| 35 |
Correct |
12 ms |
22228 KB |
Output is correct |
| 36 |
Correct |
246 ms |
22228 KB |
Output is correct |
| 37 |
Correct |
23 ms |
22228 KB |
Output is correct |
| 38 |
Correct |
31 ms |
22228 KB |
Output is correct |
| 39 |
Correct |
92 ms |
22228 KB |
Output is correct |
| 40 |
Correct |
43 ms |
22228 KB |
Output is correct |
| 41 |
Correct |
272 ms |
22228 KB |
Output is correct |
| 42 |
Correct |
43 ms |
22228 KB |
Output is correct |
| 43 |
Correct |
263 ms |
22228 KB |
Output is correct |
| 44 |
Correct |
179 ms |
22228 KB |
Output is correct |
| 45 |
Correct |
375 ms |
22228 KB |
Output is correct |
| 46 |
Correct |
30 ms |
22228 KB |
Output is correct |
| 47 |
Correct |
511 ms |
22228 KB |
Output is correct |
| 48 |
Correct |
321 ms |
22456 KB |
Output is correct |
| 49 |
Correct |
324 ms |
22456 KB |
Output is correct |
| 50 |
Correct |
226 ms |
22456 KB |
Output is correct |
| 51 |
Correct |
48 ms |
22456 KB |
Output is correct |
| 52 |
Correct |
357 ms |
22456 KB |
Output is correct |
| 53 |
Correct |
358 ms |
22456 KB |
Output is correct |
| 54 |
Correct |
354 ms |
22456 KB |
Output is correct |
| 55 |
Correct |
353 ms |
22456 KB |
Output is correct |
| 56 |
Correct |
445 ms |
22456 KB |
Output is correct |
| 57 |
Correct |
84 ms |
22456 KB |
Output is correct |
| 58 |
Correct |
9 ms |
22456 KB |
Output is correct |
| 59 |
Correct |
353 ms |
22456 KB |
Output is correct |
| 60 |
Correct |
102 ms |
22456 KB |
Output is correct |
