Submission #1004704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004704		MilosMilutinovic	날다람쥐 (JOI14_ho_t4)	C++14	100 / 100	194 ms	30900 KiB

2014_ho_t4

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, x;
  cin >> n >> m >> x;
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    --u; --v;
    if (w <= h[u]) {
      g[u].emplace_back(v, w);
    }
    if (w <= h[v]) {
      g[v].emplace_back(u, w);
    }
  }
  const long long inf = (long long) 1e18;
  vector<vector<long long>> dist(n, vector<long long>(2, inf));
  dist[0][1] = 0;
  dist[0][0] = x;
  vector<int> cur(n);
  cur[0] = x;
  set<tuple<long long, int, int>> st;
  st.emplace(dist[0][0], 0, 0);
  st.emplace(dist[0][1], 0, 1);
  vector<vector<bool>> was(n, vector<bool>(2));
  while (!st.empty()) {
    auto it = st.begin();
    long long d = get<0>(*it);
    int v = get<1>(*it);
    int t = get<2>(*it);
    st.erase(it);
    if (was[v][t] || d != dist[v][t]) {
      continue;
    }
    was[v][t] = true;
    int c = (t == 0 ? 0 : cur[v]);
    for (auto& e : g[v]) {
      int u = e.first;
      int w = e.second;
      if (c <= w) {
        if (dist[u][0] > dist[v][t] + 2 * w - c) {
          dist[u][0] = dist[v][t] + 2 * w - c;
          st.emplace(dist[u][0], u, 0);
        }
      } else {
        int nc = c - w;
        if (dist[u][1] > dist[v][t] + w + max(0, nc - h[u])) {
          dist[u][1] = dist[v][t] + w + max(0, nc - h[u]);
          cur[u] = min(h[u], nc);
          st.emplace(dist[u][1], u, 1);
        }
      }
    }
  }
  long long res = min(dist[n - 1][0] + h[n - 1], dist[n - 1][1] + h[n - 1] - cur[n - 1]);
  if (res >= inf) {
    cout << -1 << '\n';
  } else {
    cout << res << '\n';
  }
  return 0;
}

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