結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
![]() |
提出日時 | 2025-01-25 14:18:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 462 ms / 2,000 ms |
コード長 | 1,555 bytes |
コンパイル時間 | 6,041 ms |
コンパイル使用メモリ | 333,452 KB |
実行使用メモリ | 22,600 KB |
最終ジャッジ日時 | 2025-01-25 23:15:03 |
合計ジャッジ時間 | 18,453 ms |
ジャッジサーバーID (参考情報) |
judge7 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define all(x) (x).begin(), (x).end() #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for(int i = (int)(n - 1); i >= 0; i--) template <typename T> bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template <typename T> bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} using ll = long long; #define int ll using vi = vector<int>; using vvi = vector<vector<int>>; using vb = vector<bool>; using vvb = vector<vector<bool>>; using vs = vector<string>; using pii = pair<int, int>; /* using mint = modint; using vm = vector<mint>; using vvm = vector<vector<mint>>; */ signed main(){ const int inf = 1ll << 60; int n, m, p, y; cin >> n >> m >> p >> y; vector g(n, vector<pii>(0)); while(m--){ int a, b, c; cin >> a >> b >> c; a--; b--; g.at(a).emplace_back(b, c); g.at(b).emplace_back(a, c); } vi shop(n, -1); while(p--){ int place, price; cin >> place >> price; place--; shop.at(place) = price; } int ans = 0; priority_queue<pii, vector<pii>, greater<>> dijk; dijk.emplace(0, 0); vi d(n, inf); d.at(0) = 0; while(!dijk.empty()){ auto [cost, from] = dijk.top(); dijk.pop(); if(cost > d.at(from)) continue; for(auto &[to, c] : g.at(from)){ if(cost + c >= y) continue; if(!chmin(d.at(to), cost + c)) continue; dijk.emplace(cost + c, to); } } rep(i, n) if(shop.at(i) != -1) chmax(ans, (y - d.at(i)) / shop.at(i)); cout << ans << endl; }