結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー biotea
提出日時 2025-01-25 14:04:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 400 ms / 2,000 ms
コード長 1,277 bytes
コンパイル時間 1,968 ms
コンパイル使用メモリ 170,308 KB
実行使用メモリ 30,116 KB
最終ジャッジ日時 2025-04-23 18:25:20
合計ジャッジ時間 16,376 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:33:10: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   33 |     auto [di, v] = pq.top();
      |          ^
main.cpp:37:16: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   37 |     for (auto& [to, cost] : g[v]) {
      |                ^

ソースコード

diff # 

// #include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = (1LL << 61);
ll dx[4] = {0, 1, 0, -1};
ll dy[4] = {-1, 0, 1, 0};
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define REP(i, init, n) for (ll i = (ll)init; i < (ll)(n); ++i)
// ll op(ll a, ll b) { return max(a, b); }
// ll e() { return -inf; }
ll a[200010], b[200010], c[200010], d[200010], e[200010];
ll Q[200010];
int main() {
  ll n, m, p, y;
  cin >> n >> m >> p >> y;
  vector<vector<pair<ll, ll>>> g(n);
  rep(i, m) {
    cin >> a[i] >> b[i] >> c[i];
    g[a[i] - 1].push_back({b[i] - 1, c[i]});
    g[b[i] - 1].push_back({a[i] - 1, c[i]});
  }
  rep(i, p) {
    cin >> d[i] >> e[i];
    Q[d[i] - 1] = e[i];
  }
  using P = pair<ll, ll>;
  priority_queue<P, vector<P>, greater<>> pq;
  vector<ll> dist(n, inf);
  pq.push({0, 0});
  dist[0] = 0;
  while (pq.size()) {
    auto [di, v] = pq.top();
    pq.pop();
    if (dist[v] < di)
      continue;
    for (auto& [to, cost] : g[v]) {
      if (di + cost < dist[to]) {
        dist[to] = di + cost;
        pq.push({dist[to], to});
      }
    }
  }
  ll ans = 0;
  rep(i, n) {
    if (Q[i] != 0) {
      auto R = max(y - dist[i], 0ll);
      ans = max(ans, R / Q[i]);
    }
  }
  cout << ans << endl;
}
0