結果

問題 No.3013 ハチマキ買い星人
ユーザー a01sa01to
提出日時 2025-02-02 00:23:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 563 ms / 2,000 ms
コード長 1,137 bytes
コンパイル時間 5,193 ms
コンパイル使用メモリ 285,772 KB
実行使用メモリ 22,372 KB
最終ジャッジ日時 2025-02-02 00:23:24
合計ジャッジ時間 19,198 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
  #include "settings/debug.cpp"
#else
  #define Debug(...) void(0)
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

int main() {
  ll n, m, p, y;
  cin >> n >> m >> p >> y;
  vector Graph(n, vector<pair<ll, ll>>(0));
  vector<ll> price(n, -1);
  rep(_, m) {
    ll a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    Graph[a].push_back({ b, c });
    Graph[b].push_back({ a, c });
  }
  rep(_, p) {
    ll d, e;
    cin >> d >> e;
    --d;
    price[d] = e;
  }
  constexpr ll INF = 1e18;
  vector<ll> dist(n, INF);
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
  pq.push({ 0, 0 });
  dist[0] = 0;
  while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop();
    if (dist[v] < d) continue;
    for (auto [u, c] : Graph[v]) {
      if (dist[u] > d + c) {
        dist[u] = d + c;
        pq.push({ dist[u], u });
      }
    }
  }
  ll ans = 0;
  rep(i, n) {
    if (price[i] == -1) continue;
    ans = max(ans, (y - dist[i]) / price[i]);
  }
  cout << ans << endl;
  return 0;
}
0