Submission #1202621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202621		29ChuManhTich	날다람쥐 (JOI14_ho_t4)	C++20	100 / 100	127 ms	29864 KiB

2014_ho_t4

#include <bits/stdc++.h>
using namespace std;

#define NAME "FOX"
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const ll maxn = 2e5 + 11;
const ll INF = 1e15;

ll n, m;
ll x;
vector<ii> adj[maxn];
ll d[maxn];
ll h[maxn];

signed main() {
    if (fopen(NAME ".INP", "r")) {
        freopen(NAME ".INP", "r", stdin);
        freopen(NAME ".OUT", "w", stdout);
    }
    fastIO;

    cin >> n >> m >> x;
    FOR(i, 1, n) {
        cin >> h[i];
        d[i] = -INF;
    }

    FOR(i, 1, m) {
        ll u, v, w; cin >> u >> v >> w;
        if (h[u] >= w) adj[u].push_back({w, v});
        if (h[v] >= w) adj[v].push_back({w, u});
    }

    priority_queue<ii> pq;
    pq.push({x, 1});

    while (!pq.empty()) {
        ii top = pq.top(); pq.pop();
        ll pos = top.fi, u = top.se;
        if (d[u] != -INF) continue;
        d[u] = pos;
        for (auto i : adj[u]) {
            ll cost = i.fi, v = i.se;
            if (d[v] == -INF) {
                ll next = min(pos - cost, h[v]);
                pq.push({next, v});
            }
        }
    }

    if (d[n] == -INF) cout << -1;
    else cout << x + h[n] - 2 * d[n];

    return 0;
}

Compilation message (stderr)

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen(NAME ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen(NAME ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50