結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
![]() |
提出日時 | 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]) { | ^
ソースコード
// #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; }