結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー Nichi10p
提出日時 2025-01-28 19:15:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 382 ms / 2,000 ms
コード長 1,065 bytes
コンパイル時間 2,073 ms
コンパイル使用メモリ 208,292 KB
実行使用メモリ 18,280 KB
最終ジャッジ日時 2025-01-28 19:15:17
合計ジャッジ時間 15,114 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for (auto i{s}; i < t; ++i)
typedef long long ll;

template<typename T> bool chmin(T &a, T const &x) { return x < a ? a = x, true : false; }
template<typename T> bool chmax(T &a, T const &x) { return x > a ? a = x, true : false; }

int main() {
  ll N, M, P, Y;
  cin >> N >> M >> P >> Y;
  vector G(N, vector<pair<int,int>>{});
  vector C(N, 1<<30);
  rep(_, 0, M) {
    int a, b, c;
    cin >> a >> b >> c;
    --a; --b;
    G[a].emplace_back(b, c);
    G[b].emplace_back(a, c);
  }
  rep(_, 0, P) {
    int d, e;
    cin >> d >> e;
    --d;
    C[d] = e;
  }

  constexpr ll inf{(1LL << 62) - 1};
  vector D(N, inf);
  priority_queue pq(greater{}, vector<pair<ll,int>>{});
  D[0] = 0;
  pq.emplace(0, 0);
  while (!pq.empty()) {
    auto const [d, u] = pq.top();
    pq.pop();
    if (D[u] < d)
      continue;
    for (auto const &[v, c] : G[u])
      if (chmin(D[v], d+c))
        pq.emplace(d+c, v);
  }

  ll ans{0};
  rep(i, 0, N)
    chmax(ans, (Y - D[i]) / C[i]);
  cout << ans << endl;
}
0