oj.uz

Submission #761945

# Submission time Handle Problem Language Result Execution time Memory
761945 2023-06-20T12:24:31 Z hgmhc None (JOI14_ho_t4) C++17
0 / 100
 144 ms 15664 KB 
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define all(x) begin(x),end(x)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
using namespace std;
using ll = long long;
using ii = pair<int,int>;
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const ll INF = 1e18;
const int N = 1e5+3;
int n, m, x, h[N];
vector<ii> adj[N];
ll k[N];

int main() {
    scanf("%d%d%d", &n, &m, &x);
    rep(i,1,n) scanf("%d", &h[i]);
    rep(i,1,m) {
        int u, v, t;
        scanf("%d%d%d", &u, &v, &t);
        adj[u].push_back({v,t});
        adj[v].push_back({u,t});
    }
    fill(k,k+N,INF);
    priority_queue<pair<ll,int>> pq;
    k[1] = 0, pq.push({-k[1],1});
    while (not empty(pq)) {
        auto [d,a] = pq.top(); pq.pop(), d=-d;
        if (k[a] < d) continue;
        for (auto [b,t] : adj[a]) {
            if (h[a] >= t and k[b] > k[a]+t) {
                k[b] = k[a]+2*t;
                pq.push({-k[b],b});
            }
        }
    }
    if (h[n]+k[n] >= INF) puts("-1");
    else printf("%lld", h[n]+k[n]);
    // rep(i,1,n) dbg("%lld ", k[i]);
}

Compilation message

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d%d", &n, &m, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:20:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     rep(i,1,n) scanf("%d", &h[i]);
      |                ~~~~~^~~~~~~~~~~~~
2014_ho_t4.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d%d%d", &u, &v, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Incorrect 3 ms 3552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 14468 KB Output is correct
2 Correct 108 ms 15664 KB Output is correct
3 Correct 67 ms 10184 KB Output is correct
4 Correct 135 ms 15564 KB Output is correct
5 Correct 98 ms 15296 KB Output is correct
6 Correct 6 ms 4180 KB Output is correct
7 Correct 110 ms 14168 KB Output is correct
8 Correct 144 ms 14572 KB Output is correct
9 Correct 99 ms 13656 KB Output is correct
10 Correct 70 ms 11956 KB Output is correct
11 Correct 13 ms 4848 KB Output is correct
12 Incorrect 69 ms 11568 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Incorrect 3 ms 3552 KB Output isn't correct
3 Halted 0 ms 0 KB -