oj.uz

Submission #55207

# Submission time Handle Problem Language Result Execution time Memory
55207 2018-07-06T10:33:06 Z Costin Andrei Oncescu(#1304) None (JOI14_ho_t4) C++11
0 / 100
 372 ms 16676 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)
        for (auto e : v[i])
            if (h[i] >= e.second && e.second >= maxH[i])
                updateAns (X - maxH[i] + 2LL * e.second - maxH[i] + minD[e.first]);
printf ("%lld\n", ans);

return 0;
}

Compilation message

2014_ho_t4.cpp: In function 'void read()':
2014_ho_t4.cpp:12:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &N, &M, &X);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:14:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &h[i]);
         ~~~~~~^~~~~~~~~~~~~
2014_ho_t4.cpp:17:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         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]});
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 16676 KB Output is correct
2 Correct 250 ms 16676 KB Output is correct
3 Correct 210 ms 16676 KB Output is correct
4 Correct 325 ms 16676 KB Output is correct
5 Correct 242 ms 16676 KB Output is correct
6 Correct 12 ms 16676 KB Output is correct
7 Incorrect 323 ms 16676 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -