# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1202618 | 29ChuManhTich | 날다람쥐 (JOI14_ho_t4) | C++20 | 143 ms | 29908 KiB |
#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, int>
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int maxn = 2e5 + 11;
const ll INF = 1e15;
int 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) {
int 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();
int 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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |