# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
55205 | 2018-07-06T10:30:06 Z | Costin Andrei Oncescu(#1304) | 날다람쥐 (JOI14_ho_t4) | C++11 | 336 ms | 16852 KB |
#include<bits/stdc++.h> using namespace std; int X, N, M, a[300009], b[300009], t[300009], maxH[100009], h[100009]; const long long INF = 1LL << 60; long long ans = -1, minD[100009]; vector < pair < int, int > > v[100009]; void read () { scanf ("%d %d %d", &N, &M, &X); for (int i=1; i<=N; i++) scanf ("%d", &h[i]); for (int i=1; i<=M; i++) scanf ("%d %d %d", &a[i], &b[i], &t[i]), v[a[i]].push_back ({b[i], t[i]}), v[b[i]].push_back ({a[i], t[i]}); } void updateAns (long long val) { if (ans == -1 || val < ans) ans = val; } priority_queue < pair < int, int > > maxHPQ; void buildMaxH () { for (int i=1; i<=N; i++) maxH[i] = -1; maxH[1] = X, maxHPQ.push ({X, 1}); while (!maxHPQ.empty ()) { auto curr = maxHPQ.top (); maxHPQ.pop (); if (maxH[curr.second] != curr.first) continue; int nod = curr.second; maxH[nod] = min (maxH[nod], h[nod]); for (auto it : v[nod]) if (maxH[it.first] < maxH[nod] - it.second) maxH[it.first] = maxH[nod] - it.second, maxHPQ.push ({maxH[it.first], it.first}); } if (maxH[N] != -1) updateAns (X - maxH[N] + h[N] - maxH[N]); } priority_queue < pair < long long, int > > PQ; void buildMinD () { for (int i=1; i<=N; i++) minD[i] = INF; minD[N] = h[N], PQ.push ({-h[N], N}); while (!PQ.empty ()) { auto curr = PQ.top (); PQ.pop (); if (minD[curr.second] != -curr.first) continue; int nod = curr.second; for (auto it : v[nod]) if (it.second <= h[it.first] && 2LL * it.second + minD[nod] < minD[it.first]) minD[it.first] = 2LL * it.second + minD[nod], PQ.push ({-minD[it.first], it.first}); } } int main () { //freopen ("input", "r", stdin); //freopen ("output", "w", stdout); read (); buildMaxH (); buildMinD (); for (int i=1; i<=N; i++) if (maxH[i] != -1 && minD[i] < INF) updateAns (X + minD[i]); printf ("%lld\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 5 ms | 3044 KB | Output is correct |
3 | Incorrect | 5 ms | 3092 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 270 ms | 16832 KB | Output is correct |
2 | Correct | 216 ms | 16832 KB | Output is correct |
3 | Correct | 139 ms | 16832 KB | Output is correct |
4 | Correct | 269 ms | 16832 KB | Output is correct |
5 | Correct | 179 ms | 16832 KB | Output is correct |
6 | Correct | 11 ms | 16832 KB | Output is correct |
7 | Correct | 239 ms | 16852 KB | Output is correct |
8 | Correct | 336 ms | 16852 KB | Output is correct |
9 | Correct | 279 ms | 16852 KB | Output is correct |
10 | Correct | 153 ms | 16852 KB | Output is correct |
11 | Correct | 28 ms | 16852 KB | Output is correct |
12 | Correct | 172 ms | 16852 KB | Output is correct |
13 | Correct | 119 ms | 16852 KB | Output is correct |
14 | Correct | 303 ms | 16852 KB | Output is correct |
15 | Correct | 12 ms | 16852 KB | Output is correct |
16 | Correct | 257 ms | 16852 KB | Output is correct |
17 | Correct | 21 ms | 16852 KB | Output is correct |
18 | Correct | 56 ms | 16852 KB | Output is correct |
19 | Correct | 129 ms | 16852 KB | Output is correct |
20 | Correct | 43 ms | 16852 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 5 ms | 3044 KB | Output is correct |
3 | Incorrect | 5 ms | 3092 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |