結果
問題 |
No.3013 ハチマキ買い星人
|
ユーザー |
|
提出日時 | 2025-01-26 11:29:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,035 ms / 2,000 ms |
コード長 | 2,616 bytes |
コンパイル時間 | 2,198 ms |
コンパイル使用メモリ | 184,596 KB |
実行使用メモリ | 61,616 KB |
最終ジャッジ日時 | 2025-01-26 11:29:37 |
合計ジャッジ時間 | 24,249 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
# include <bits/stdc++.h> # include <atcoder/modint> # include <atcoder/segtree> # include <atcoder/lazysegtree> # include <atcoder/dsu> //# include <regex> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<vector<vector<int>>> vvvi; typedef vector<long long> vl; typedef vector<vector<long long>> vvl; typedef vector<vector<vector<long long>>> vvvl; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; typedef vector<vector<vector<bool>>> vvvb; #define rep(i,n) for(int i=0;i<n;i++) #define reps(i,m,n) for(int i=m;i<n;i++) #define repl(i,n) for(ll i=0;i<n;i++) #define repsl(i,m,n) for(ll i=m;i<n;i++) #define repr(i,n) for(int i=n-1;i>=0;i--) #define repsr(i,m,n) for(int i=n-1;i>=m;i--) #define replr(i,n) for(ll i=n-1;i>=0;i--) #define repslr(i,m,n) for(ll i=n-1;i>=m;i--) #define sksort(x) sort(x.begin(), x.end()) #define sksortr(x) sort(x.rbegin(), x.rend()) #define disp(x) cout << x << endl #define disps(x) cout << x << " " #define dispe cout << endl #define dispv(x) for(ll xqzj=0;xqzj<(ll)x.size();xqzj++){disps(x[xqzj]);}dispe #define dispvv(x) for(ll xqzi=0;xqzi<(ll)x.size();xqzi++){dispv(x[xqzi]);} #define dispy cout << "Yes" << endl #define dispn cout << "No" << endl #define dispyn(x) if(x)dispy;else dispn #define dispd cout << std::setprecision(20) #define inp(x) int x;cin>>x #define inpl(x) ll x;cin>>x #define inps(x) string x;cin>>x #define allv(x) (x).begin(),(x).end() #define allrv(x) (x).rbegin(),(x).rend() #define imax(x,y) x=max(x,y) #define imin(x,y) x=min(x,y) using mint = atcoder::modint998244353; int main(){ inp(n); inp(m); inp(p); inpl(y); vector<set<int>> g(n); map<pair<int,int>,ll> c; vl h(n,1000000000000000001); rep(i,m){ inp(a); inp(b); g[a-1].insert(b-1); g[b-1].insert(a-1); inpl(t); c[{a-1,b-1}]=t; c[{b-1,a-1}]=t; } rep(i,p){ inp(d); inpl(e); h[d-1]=e; } set<pair<ll,int>> st; st.insert({0,0}); vl b(n,1000000000000000001); b[0]=0; while(st.size()>0){ pair<ll,int> q=*st.begin(); st.erase(*st.begin()); for(int i:g[q.second]){ ll x=q.first+c[{q.second,i}]; if(b[i]==1000000000000000001){ b[i]=x; st.insert({b[i],i}); }else if(b[i]>x){ st.erase({b[i],i}); b[i]=x; st.insert({b[i],i}); } } } ll ans=0; rep(i,n)imax(ans,(y-b[i])/h[i]); disp(ans); }